‘ of the upper left corner and coordinates of the right lower corner.
Sub ColourFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer, Vcolour As Integer)
Dim Stk As String
Stk = R1C1_to_A1(Vtop, Vleft) & “:” & R1C1_to_A1(Vbottom, Vright)
Sheets(2).Range(Stk).Interior.ColorIndex = Vcolour ’Vcolour есть номер цвета в цветовой схеме.
‘ .ColorIndex = 34 ‘Vcolour there is number of the colour in color scheme.
End Sub
Function R1C1_to_A1(Vrow As Integer, Vcol As Integer) As String
V26 = “ABCDEFGHIJKLMNOPQRSTUVWXVZ”
Dim Stk As String
If Vcol > 26 Then
Stk = Mid(V26, Int(Vcol / 26), 1) + Mid(V26, (Vcol Mod 26), 1) + CStr(Vrow)
Else
Stk = Mid(V26, Vcol, 1) + CStr(Vrow)
End If
R1C1_to_A1 = Stk
End Function
Private Sub CalcColB()
‘Вычисление ключевого столбца по найбольшей оценке(когда min)
‘Calculation key column on the largest estimation(when min)
Dim i As Integer
Dim WrcM As Double, IrcM As Integer
Dim WrcC As Double, IrcC As Integer
WrcM = 0
WrcC = 0
For i = 1 To MaxX
If Tsimp(AmRest + 1, i) > WrcM Then
WrcM = Tsimp(AmRest + 1, i)
IrcM = i
ElseIf Tsimp(AmRest + 2, i) > WrcC And Tsimp(AmRest + 1, i) = 0 Then
WrcC = Tsimp(AmRest + 2, i)
IrcC = i
End If
Next i
If WrcM > 0 Then
Icol = IrcM
ElseIf WrcC > 0 Then
Icol = IrcC
Else
Icol = 0
End If
End Sub
Private Sub CalcColL()
‘Вычисление ключевого столбца по отрицательной(максимальной по модулю) оценке(когда max)
‘Calculation key column on negative(maximum modulo) to estimation(when max)
Dim i As Integer
Dim WrcM As Double, IrcM As Integer
Dim WrcC As Double, IrcC As Integer
WrcM = 0
WrcC = 0
For i = 1 To MaxX
If Tsimp(AmRest + 1, i) < 0 And Abs(Tsimp(AmRest + 1, i)) > WrcM Then
WrcM = Abs(Tsimp(AmRest + 1, i))
IrcM = i
ElseIf (Tsimp(AmRest + 2, i) < 0) And (Abs(Tsimp(AmRest + 2, i)) > WrcC) And (Tsimp(AmRest + 1, i) = 0) Then
WrcC = Abs(Tsimp(AmRest + 2, i))
IrcC = i
End If
Next i
If WrcM > 0 Then
Icol = IrcM
ElseIf WrcC > 0 Then
Icol = IrcC
Else
Icol = 0
End If
End Sub
Private Sub CalcRow()
‘Вычисление ключевой строки по положительному минимум отношения X0/Xi
‘Calculation of the key line on positive minimum relations X0/Xi
Dim Cslave As Double, Islave As Integer
Dim Wrk As Double
If Icol = 0 Then
For i = 1 To AmRest
MiCiXiAi(i, 4) = -1
‘MiCiXiAi(i, 4) = Nothing
Next i
Irow = 0
Else
Cslave = -1
Islave = 0
For i = 1 To AmRest
If Tsimp(i, Icol) <> 0 Then
If Tsimp(i, 0) = 0 Then
Wrk = IIf(Sgn(Tsimp(i, Icol)) = 1, 0, -1)
Else
Wrk = Tsimp(i, 0) / Tsimp(i, Icol)
End If
MiCiXiAi(i, 4) = Wrk
If Wrk >= 0 And Islave = 0 Then
Cslave = Wrk
Islave = i
ElseIf Wrk >= 0 Then
If DirectCycle Then
If Wrk < Cslave Then ’оставлять из равных первый
Cslave = Wrk
Islave = i
End If
Else
If Wrk <= Cslave Then ‘оставлять из равных последний
Cslave = Wrk
Islave = i
End If
End If
End If
Else
MiCiXiAi(i, 4) = -1
End If
Next i
Irow = Islave
End If
End Sub
Private Sub CommandButton2_Click()
‘Совершить итерацию
Dim Welm As Double
MiCiXiAi(Irow, 1) = Tsimp(AmRest + 3, Icol)
MiCiXiAi(Irow, 2) = Tsimp(0, Icol)
MiCiXiAi(Irow, 3) = Icol
Welm = Tsimp(Irow, Icol)
For i = 1 To AmRest + 2
If i <> Irow Then
For j = 0 To MaxX
If j <> Icol Then
Tsimp(i, j) = Tsimp(i, j) - (Tsimp(i, Icol) / Welm) * Tsimp(Irow, j)
End If
Next j
End If
Next i
For j = 0 To MaxX
Tsimp(Irow, j) = Tsimp(Irow, j) / Welm
Next j
For i = 1 To AmRest + 2
Tsimp(i, Icol) = 0
Next i
Tsimp(Irow, Icol) = 1
FRowCol
If Cycle() Then
LookResult “Итерации зациклились на итерации №” & CStr(NumIter - 1), 11
ElseIf Icol > 0 And Irow > 0 Then
LookResult “Смотри итерацию №” & CStr(NumIter - 1), 50
ElseIf Icol > 0 And Irow <= 0 Then
LookResult “Функция не ограничена”, 28
Else
LookResult “Оптимальный план”, 37
End If
End Sub
Private Sub FRowCol()
‘Поиск разрешающих строки и столбца
If MaxLi Then
CalcColL ’max
Else
CalcColB ’ min
End If
CalcRow ’X0/Xi
If Icol > 0 And Irow > 0 Then
CommandButton2.Visible = True
NumIter = NumIter + 1
CommandButton2.Caption = “Произвести итерацию №” & CStr(NumIter)
Else
NumIter = NumIter + 1
CommandButton2.Visible = False
End If
End Sub
Private Function Cycle() As Boolean ‘Если “Верно” зациклились. If “True” were looped.
Dim CurrentPlan As String
Dim i As Integer
Cycle = False
CurrentPlan = “”
For i = 1 To AmRest
CurrentPlan = CurrentPlan & CStr(MiCiXiAi(i, 3))
Next i
If InStr(AllPlans, CurrentPlan) > 0 Then
If DirectCycle = True Then
DirectCycle = False
Else
Cycle = True
End If
AllPlans = “”
Else
AllPlans = AllPlans & ” ” & CurrentPlan
End If
End Function
Заключение
В данной работе рассматриваются два способа решения исходной задачи линейного программирования.
Первый заключается в том, что сначала решается вспомогательная задача (L-задача), позволяющая построить начальный опорный план, затем на основе этого найденного плана решается исходная задача (определяется ее оптимальный план). Второй способ является объединением двух этапов и состоит в решении расширенной задачи (M-задачи), также приводящей к нахождению оптимального плана исходной задачи.
Вычислительную основу этих двух способов решения составляют соответственно первый и второй алгоритмы симплекс-метода. Один из параметров, по которому может быть оценен любой итерационный алгоритм – количество шагов, приводящих к решению задачи или установлению ее неразрешимости. Для данной задачи наиболее эффективным методом оказался первый метод(L-задача + исходная задача), т.к. он привел к решению за 4 шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов, вероятно, обусловлена неоднозначность выбора разрешающего элемента в исходной таблице L-задачи.
Сравнение количества вычислений на каждой итерации приводит к следующим оценочным результатам рассматриваемых алгоритмов. Преимущественная часть вычислений на каждом шаге алгоритмов определяется размерностью главной части таблицы (в первом алгоритме) или основной таблицы (во втором алгоритме). В первом случае она имеет размерность (m+1)x(n+1), во втором - (m+1)x(m+1). Даже учитывая, что второй алгоритм требует построения вспомогательной таблицы, он оказывается более компактным.
Еще одно несомненное достоинство второго алгоритма заключается в возможности определения оптимального плана двойственной задачи из (m+1)-й строки основной таблицы, соответствующей последней итерации, без всяких дополнительных вычислений.
Список использованных источников
Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2001.
Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. – М.: Издательство Московского университета, 1997.
Исследование операций в экономике /Под ред. Кремер. – М.: ЮНИТИ, 1997.
Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М.: Высшая школа, 1986.
Шикин Е.В., Чхартишвили А.Г. Математические методы и модели управления. – М.: Дело, 2000.
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.
Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.
Липски В. Комбинаторика для программистов. – М.: Мир, 1988.
30