korobov

121

113

Продолжение табл. 3.6

122

114

Продолжение табл. 3.6

123

Однако мы не знаем, является ли это решение оптимальным, т. е. дают ли значения неизвестных минимум целевой функции исходной задачи (3.16). С этой целью надо приступить к ее решению. Для этого составляем первую симплексную таблицу (табл. 3.7), используя последнюю таблицу вспомогательной задачи. Как было указано выше, отбросим столбцы, соответствующие искусственным переменным, и заменим показатели критерия оптимальности на коэффициенты целевой функции 3.16):

F = 0,5x1 + 0,6x2 + 0,4x3 + 0,2x4 + 0,3x5 = min.

При этом для упрощения вычислений коэффициент 0,1 вынесем за скобки с тем, чтобы избавиться от дробности этого показателя при вычислениях в симплексной таблице.

Оказалось, что в строке этой первой таблицы не содержится ни одной двойственной оценки, превышающей значение ноля. Это свидетельствует о том, что найдено оптимальное решение исходной задачи (3.16), (3.17), обеспечивающее минимальное значение ее целевой функции.

В этом примере уже первая программа решения исходной задачи оказалась оптимальной. Она характеризуется следующими значениями базисных неизвестных (с учетом коэффициента упрощения 100).

124

азначения свободных неизвестных x2, x5, x7, х8, х9 равны нулю.

Вдругих примерах первая программа может оказаться не оптимальной. В таком случае ее надо довести до оптимальной способом последовательного улучшения плана, т.е. выполнить столько итеративных вычислений, сколько потребуется для получения оптимального решения.

Оптимальное решение найдено; остается проверить результаты. Для этого

подставляют значения неизвестных х1, х2, .... х5 в первоначальные неравенства и целевую функцию. В нашем примере оптимальное решение исходной задачи (значения базисных неизвестных) совпало с последним планом вспомогательной задачи, проверку которого мы сделали выше. Поэтому нет необходимости повторно подставлять значения неизвестных в первоначальные ограничительные неравенства — они удовлетворяют условию задачи.

Подставим значения неизвестных в целевую функцию (3.16)

F = 0,5 2003 + 0,6 0 + 0,410003 + 0,2 200 + 0,3 0 = 6203 = min.

Далее рассмотрим второй способ решения этой задачи. Он в значительной мере отличается от первого хотя бы тем, что здесь не требуется решать вспомогательную задачу для отыскания опорного плана (какого-то решения) исходной задачи. Этот способ позволяет нам приступить к непосредственному решению исходной задачи, поскольку в симплексных уравнениях, представленных в окончательной форме, имеется единичная подматрица.

Искусственные переменные у1, y2, y3 и y4 входят в первоначальную программу, с которой начинается процесс решения задачи, как базисные с положительными значениями, но по ходу решения они постепенно исключаются из базисных переменных. Оптимальной программа станет не раньше, чем все эти искусственные переменные перейдут из базисных в свободные. Чтобы это обеспечить, искусственные неизвестные вводятся в уравнение целевой функции с коэффициентами (ценами), равными М.

Под М понимается величина больше любого другого сколько угодно большего наперед заданного числа. Таким образом, мы блокируем искусственные неизвестные, т. е. введением коэффициентов М мы избавляемся от влияния искусственных переменных на истинную оптимальную программу. Действительно, как только хотя бы одна из искусственных переменных в программе положительна, значение целевой функции

125

расширенной задачи (с искусственными переменными), соответствующим подбором положительного числа М, может быть сделано больше любого значения целевой функции (3.16) исходной задачи при любых значениях основных переменных х1, x2, x3, x4, х5. Следовательно, минимум целевой функции может быть получен только при нулевых значениях искусственных переменных.

Целевая функция нашей задачи примет следующее выражение:

F = 0,5x1 + 0,6x2 + 0,4x3 + 0,2x4 + 0,3x5-0x6-0x7-0x8 -0 x9+My1+ My2+ My3+ My4 = min или с учетом сокращения на 0,1:

F = 5x1 + 6x2 + 4x3 + 2x4 + 3x5-0x6-0x7-0x8 -0 x9+My1+ My2+ My3+ My4 = min

Теперь все готово для решения задачи. Можно приступить к составлению первой симплексной табл. (3.8), которая будет иметь точно такой же вид, как и в задачах, рассмотренных ранее1. В первоначальную программу войдут все искусственные переменные. Однако есть и некоторая особенность таблицы, заключающаяся в том, что в задачу входит неопределенное число М.

Исходная программа P1 характеризуется следующими значениями переменных: y1= 5, y2=10, y3=2, y4=4, все остальные неизвестные равны нулю.

Поскольку М рассматривается как обычное число, исходная величина целевой функции F1' определяется, как

F1' =M 5+M 10+ M 2+ M 4=21M,

что и записано в клетке F1.

Далее вычисляем двойственные оценки и записываем их в оценочную строку. Для столбца x1 она будет равна 5М – 5

1=(0 M+2 M+3 M+0 M)-5=5M-5.

В результате получилось составное число. Поскольку величина М сколь угодно велика, может возникнуть вопрос: зачем надо умножать или тем более прибавлять к этому числу или вычитать из него ничтожно малые по сравнению с ним числа? Однако в процессе решения задачи абсолютная величина двойственных оценок не играет какой-либо существенной роли, важны соотношения между ними. И может оказаться, что одно составное число больше или меньше другого составного именно на сравнительно небольшую величину. К тому же и в ходе вычислений из некоторых составных чисел будут исключены М, и о величине соответствующих оценок надо будет судить по цифровой их части.

Все дальнейшие действия осуществляются обычным порядком.

Наибольшая оценка 1 = 5M - 5 находится в столбце с неизвестной х1. Этот столбец и будет ключевым. В качестве ключевой строки принимается строка с неизвестной

у3, поскольку в ней минимальное положительное частное bi ,равное 2/3. Переходим к

αij

следующей программе, в которую введем неизвестную х1 вместо yз. Преобразуем матрицу и результат записываем в табл. 3.8 в части, соответствующей 2-й итерации.

Чтобы упростить операции с оценочной строкой, можно разделить ее на две строки. В верхней ее части следует записывать коэффициенты при М, в нижней — остальную часть соответствующего составного числа. Так, оценка столбца х2 (вычисляемая с помощью коэффициента α) должна быть

В верхней части оценочной строки в этом столбце записываем 2, а внижней — (-6). Оценка, например, столбца х5 будет

126

1 Как и в предыдущем случае, составим одну обобщенную таблицу, в которую запишем расчеты по всем итерациям.

127

128

129