§ 65. Симплекс-метод решения задач линейного программирования, М-метод
Г Симплексный метод решения задач линейного программирования часто называют методом последовательного улучшения опорного плана, так как основан на переходе от одного опорного плана к другому опорному плану, при котором значение целевой функции возрастает, если задача поставлена на максимум или уменьшается, если задача постай лена на минимум (при условии, что каждый опорный план является невырожденным). Процесс повторяется до тех пор, пока не будет получено оптимальное решение.Симплексный метод включает в себя следующие этапы.
Составление первого опорного плана.
Систему ограничений задачи, заданной в виде системы неравенств смысла (^0), переводят в систему уравнений путём зведення неотрицательных дополнительных переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, так как определитель, составленный из компонент этих векторов, отличен от нуля. Эти введённые переменные называются базисными в первом опорном плане, а основные переменные являются свободными (их можно полагать равны ми нулю). Составляют симплексную таблицу, которая состоит из коэффициентов системы ограничений. Последняя строка таблицы называется индексной. Она заполняется коэффициентами целеной функции, взятыми с противоположными знаками.
Проверка плана на оптимальность
Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательные (^0), то план является оптимальным. Если найдётся хотя бы один коэффициент ин-дексной строки меньше нуля, план не оптимальный и его можно улуч-шить, переходя к следующему этапу. При решении задачи на минимум (можно переитн к нахождению максимума функции Fj ^ — F, так как iniuF =ї — muxFi = — тах(—і7)), а признаком оптимальности плана, в этом случае, являются отрицательные значения всех коэффициентов индекснон строки.
Определение направляющих столбца к строки.
Из отрицательных коэффициентов индексной строки выбирают наи-больший по абсолютной величине.
Столбец, содержащий этот коэффициент. называется направляющим, Направляющий столбец, соответ- ст сующий выбранному коэффициенту, показывает, какая переменная па следующем этапе перейдёт на свободных в базисные. Если окажется, что наименьших равных между собой элементов индексной строки имеется несколько, то рекомендуется выбирать первый (левый) элемент. Если в направляющем столбце е некоторой таблице нее коэффициенты не положительные, то целевая функция F неограничен а на множестве допустимых планов (F —^ оо) и задачу решить нельзя.Элементы столбца свободных членов симплексной таблицы делит на соответствующие положительные элементы направляющего столбца. Результаты заносят а столбец в. Строка, соответствующая минимальному значению 0. является направляющей. Она определяет переменную. которая на следующем этапе выйдет из базиса и станет свободной.
Элемент, находящийся на пересечении направляющих столбца и строки, называется разрешающим. Направляющую строку и на-правляющий столбец отмечают стрелками, а разрешающий элемент оОводяг.
Если в столбце 0 содержится несколько одинаковых наименьших значений, то новый опорный план будет вырожденным, что может привести к многократному повторению процесса вычисления, не позволяющему завершить задачу (одна или несколько базисных переменных станут рапными нулю). Тогда делят элементы строк, имеющие 0 одина-ковые наименьшие значения на предполагаемые разрешающие элементы, результаты заносят в дополнительную таблицу. За направляющую строку выбирают ту, в которой раньше встречается меньшее число при чтении по столбцам слева направо,
4 Определение ноаого опорного плана,
Для перехода к новому опорному плану производят пересчёт сим-плексной таблицы. Сначала заменяют переменные в базисе. В базис вводят переменную, соответствующую направляющему столбцу. Разделив асе элементы направляющей строки предыдущей симплексной таблицы на разрешающий элемент, результаты деления вносят в строку следующей таблицы, соответствующую введённой в базис переменной.
На месте разрешающего элемента в следующей таблице будет стоять единица, а в остальных к летках направляющего столбца, включая клетку столбца индексной строки, записываем нули. Чтобы заполнить ц-ю строку, нужно все элемента преобразованной строки умножить на коэффициент, стоящий на пересечении fi-іл строки и направляющего столбца предыдущей таблицы и вычесть из соответствующих элементов /t-й строки этой же таблицы, а результат записать в ^-ю строку новой таблицы (см. ниже).Полученный новый план проверяют на оптимальность. Таким образом, осуществляется переход ко второму этапу v. продолжается процесс до получения оптимального шиша.Для проверки правильности вычисления па каждой строке сим-плексной таблицы вводят столбец контрольных сумм (Е). В столбце контрольных сумм первой симплексной таблицы записывают сумму всех элементов строки, В последующих таблицах над числами, стоящими а столбце проводят те же преобразования, что и над любым элементом таблицы.
582 Линейное программирование [ Гл.'Х
Для упрощения вычислений пользуются следующими правилами:
а) если э направляющем столбце таблицы имеется нуль, то строка, содержащая этот нуль, в следующую таблицу переписывается без изменения (см- Т-4 столбец и Т-5 строку хе);
б) если в направляющей строке имеется нуль, то столбец, содержа* щий этот нуль, в следующую таблицу переписывается без изменений (см, Т-1 строку И Т-2 столбцы и зв).
Проследим симплекс-метод на конкретном примере.
Задача. Найти максимум функции
F = 5 Oxi+45a2-H40x3 , О)
при условиях ^ллап
( 50xi + + 25х;Н ^ 1450,
35xi + 15х3 + 15хэ ^ Ю50, { }
х1 ^ 0, х2 ? 0tx3 ^ 0.
Решение, 1. Составление первого опорного плана. Задача записана в стандартной форме. Запишем сё в форме основной задачи линейного программирования, Для этого от неравенств перейдем к уравнениям, введя три (так как имеется три неравенства) дополнительные неотрицательные переменные Zfi, Же. Систему неравенств (2) запишем в виде системы уравнений
50.ті + 25лт2 + 25я3 + хА - 1450, 35л: і + Юх2 + 20а;3 + а* = 700, (3)
35хі + 15x2 + 15x2 + = 1050,
Систему (3) запишем в векторной форме
Ті/1] + х^А? + Хз А3 Ч- Х4Л4 + х$АБ + = (4)
Л0=\ 700 , Ах = 35 , А2 = 10 , Аз = 50 J V 35 / \ 15 /
Л4 = { 0 \ As = ( 1 \ - ( 0 V
§ 65 j Сцлтлекс-jrgfrtO'd рі?шения задач линейного программирования 533
Следовательно, в первом опорном плане исходные переменные
хз принимаем за свободные переменные (и полагаем их разными нулю), а дополнительные переменные дгб — за базисные.
В системе (3) полагаем; Xi = т2 ~ = 0, находим x
Таким образом, первый опорный план имеет видХх = (0,0,0,1450, 700,1050),
а функция F{X) - 50 0 - 45 0 - 40 - 0 + 0 ¦ ха + 0 ¦ хь + 0 ¦ 0,
Составляем первую симплексную таблицу (см. таблицу Т:1), Ин-дексную (последнюю строку таблицы) строку заполняем коэффициентами целевой функции, взятыми с противоположными знаками. Все остальные клетки таблицы Т-1 (кроме индексной н столбцов II и в) заполняются числами системы (3), В столбец контрольных сумм ЗС проставляется сумма всех элементов соответствующей строки.
Проверка плана на оптимальность,
Ясли все коэффициенты индексной строки неотрицательные (^0), то данный план является оптимальным. В рассматриваемом примере среди элементов индексной строки имеются отрицательные числа —50; —45, —40, Следовательно, составленный опорный план является неоптимальным и его можно улучшить.
Определение направляющих столбца и строки.
Находим направляющий столбец и напраеляющую строку. Из всех неотрицательных коэффициентов индексной строки выбираем наиболь-ший по абсолютной пеличине (т50). Столбец, который содержит наи-меньшее отрицательное число (—50) индексной строкиt называется направляющим и показывает, какая переменная (яі) в следующей таблице перейдёт нэ свободных в базисные. Если наименьших от-рицательных равных между собой элементов имеется несколько, то рекомендуется выбирать первый (левый) элемент.
Элементы столбца свободных переменных таблицы Т-1 делят на соответствующие положительные элементы [направляющего столбца (1450 ; 50 = 29; 700 : 35 => 20; 1050 :35 30). Результаты заносят в столбец в. Строка таблицы Т-1, соответствующая минимальному (min# ™ =- 20), является направляющей. Она показывает, какая переменная (xj) в следующей таблице выйдет из базиса и станет свободной.
Элемент, находящийся на пересечении направляющей строки и на-правляющего столбца, называется разрешающим (35) и в таблице его обводят, а направляющие столбец и строку отмечают стрелкой
Определение нового опорного плана.
Формируем следующую симплексную таблицу* т.
е, таблицу Т-2. Вместо базисной переменной, стоящей в направляющей строке таблицы Т-1 (т.е. 3:5) ставим в таблицу Т-2 переменную, стоящую и направ-ляющем столбце таблицы Т-1 (т.е. ЇЇ). Строка TJ В таблице Т-2 получается в результате деления всех элементов строки х$ в таблицеТ-1 на разрешающий элемент ^700 : 35 — 20; 35 : 35 = 1; 10 : 35 ^ = 20 : 35 = 0 : 35 = 0; 1 ; 35 = Jb 0 : 35 - 0; 76G г 35 = .
Итак, в таблице Т-2 в столбце ^базисные переметшее СТОЯТ Х4, , Хе. Строка хх заполнена числами ^20; I; 0; 0; На пересе
чении строки н столбца І'І в таблице Т-2 стоит единица, остальные элементы этого столбца полагаем равными нулю.
Для заполнения остальных клеток заметим, что взяв любое число таблицы Т-1, не входящее в направляющую строку, в направляющий столбец и столбец в, это число вместе с разрешающим элементом, направляющим столбцом н направляющей строкой образуют прямоугольник, Например, для числа 1450 числа 1450; 50; 35; 700 образуют прямоугольник. Перемножив числа направляющего столбца (50) н направляющей строки (700), находящихся по углам прямоугольника (700 ¦ 50 — 3500). разделив на разрешающий элемент (3500 : 35 = 1000) и вычтем полученное число (1000) из выбранного нами числа 1450 (1450-1000 — 450), Полученное число (450) заносим в таблицу Т-2 на то место, которое занимало прежде число (1450) в таблице T-L
Для числа 1050 находим прямоугольник (1050; 700; 35; 35). Число,
которое нужно внести в таблицу Т-2, равно 1050 — Аналогично для F в таблицу Т-2 заносим число 0 —
= 350,
36 700
35
1000.
ТОО ("50) _ 35
Заполняем столбец х2 таблицы Т-2, используя «правило прямо-угольника»
10-35
215
50 - 10
75 7
= 5;
50 10
15-
25-
-45 +
35 7 : " 35 1 35 7
Для заполнения таблицы Т-2 (и последующих) можно поступать следующим образом: после заполнения в таблице Т-2 строки xLi умножаем все элементы этой же строки на число 50
1000. 50, ™ », 0. * D, Ш
и вычитаем из строки Х4 (содержащей 50) таблицы Т-1
_ 75 25 п 10 _ 31137 450, 0, у, -у, 0,-у, 0,-у-,
это и есть первая строка таблицы Т-2.
Если умножим на -50 и вычтем из индексной строки Т-1, то получим индексную строку таблицы Т-2.Для третьей строки таблицы Т-2: умножаем преобразованную направляющую строку (строка таблицы Т-2) на число 35
700\ 35, 10, 20, 0, 1, 0, 766.
Вычитаем из третьей строки таблицы Т-1
350, 0, 5, —5, 0, -1, 1, 350,
это и есть строка таблицы Т-2.
Аналогично заполняются остальные клетки таблицы Т-2 кроме столбца 0.
§65] Симплекс-метод решения задач линейного программирования л 85
После заполнения всех клеток таблицы Г-2 мы видим, что нндекс-
{ 215\ / 80 \ лая строка содержит два отрицательных элемента (—— } u [ - — J .
Следовательно, полученный план — (20; О; 0; 450; 0; 350) не является оптимальным, при этом F(Х>г) » 1000.
Формируем третью симплексную таблицу. Выполняем последовательно все этапы вычисления, получим таблицу Т-3, из которой следует, что третий опорный план Х<4 — (S; 42; 0; 0; 0; 140), Р(Х^) ~ 2200 также не является оптимальным. В индексной строке таблицы Т-3
также два отрицательных элемента ^^ и . Б таблице Т-4 уже
один отрицательный элемент ^ —7) - ^ только в пятой таблице в ин-дексной строке все элементы неотрицательные Оптимальный опорный план имеет вид
Х5 = (0; 58; 0; О; 120; ISO), - = 2610.
Замечания.
Сели в оптимальном плане вошла дополнительная переменная, то при реализации такого плана имеются недоиспользованные ресурсы.
Если в индексной строке симплексной таблицы оптимального плана находится куль, принадлежащий свободной переменной, не входящей в базис, а в столбце, содержащий этот нуль, имеется не менее двух ненулевых элементов, из которых хотя бы один положительный, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно ев ест и в базис, взяв этот столбец за направляющий. В результате будем иметь второй оптимальный план с другим набором базисных переменных, но с тем же значением целевой функции. Согласно основной теореме линейного программирования любая выпуклая комбинация этих планов также является оптимальным планом. Общий вид решения для нахождении всего множества оптимальных планов записывается следующим об-разом;
X = aXi + (1 - где 0 ^ а < 1-
Т-1
Базисные перемен-ные Свободные переменные 3=1 ЇЗ xi ЗГ5 Е 9
34 1450 50 25 35 і 0 0 iSSt 39
¦ES 700 10 20 0 1 1 0 76G 20
хп 105D 35 15 15 0 » 1 11 16 ЗО
пхо 0 -50 —45 -40 0 0 0 max
Продолжение на следуюи{ей странице
Электронная версия книги подготовлена для открытой библиотеки учебников
§65 } Симплекс-метод решения задач линейного программирования 58/ Задание. В задачах 1-4 проверить вычисления.
Задача 1 Найти максимум функции F = 40s 1 Збхз 32&з при условиях
40xi t 20х2 + 20х3 ^ 1160, 2S.Tя + &х2 + 16х3 ^ 560, 28л; і 4 12х2 + < 340,
X} ^ О, Х2 > 0, Хъ ^ 0.
Ответ: Fmttx - ЛСД = 2088, Л* - (0S58,0,0,96,144). Задача 2 Найти максимум функции F •= 4- 70x2 + 6023 прі' условиях
Г 30xt + 30ха 4 90х3 < 8100, IQQxi 4 90x2 4 150хз ^ 9GOO, ЬОхі 4 50х2 + ІОхз ^ 2500, ! а;] ^ 0, х2 хз ^ 0.
о г n/^ \ 55750 „ /л '175 375 41100 \
Отпет; Flll(llf - = и ' А4 = (0, -ур'ТГ1 11' 1 J "
Задача 3. Найти максимум функции F = + 5Ахп 4- 43яз npj' условиях
' бОхі + гох2 -ь зага ^ то,
42хі 4І2хїї4 24х3 ? 840, 42xj 4 ISx2 -М8т3 ^ 12G0. xi > 0, хз > 0, xj ^ 0.
F(J?S) =» 3132, = (0,53,0,0,144,^16). Найти максимум функции F + 14xa 4 хз прі
{
9a:, 4- + 4ггэ < 54, ?te] 4- &X2 + 5із < 63, 22 ^ 5, ^ 0, хэ >0, xs ^ 0.
Ответ: Fmax = F(X) = 108,
X=aX4+{ (2 a; 5; 38 ~ lSa; у (1-а); 0; о) . = (2; 5; 4; 0S 0; 0); - (O; 5; ~; 0; o) 587
Таблицы к задаче І Т-1
Базисное перемен-ные Свободные переменные XI Х2 23 ®4 15 iC ? 0
Г4 II SO 40 20 20 1 0 0 1241 29
ЯЗ 560 т 8 16 0 1 0 613 20
ХЦ 840 28 12 12 0 0 ] 893 30
F 0 -40 -36 -32 0 a 0 108 max
> Г
j
14 560 0 fit! !_z_ 20 7 1 10
"T 0 25Б7 7 42
XI го 1 2 7 A
7 0 1
28 0 633 28 70
2SQ 0 4 0 -1 1 ¦ 280 70
F 800 0 172 7 04 7 0 10 7 0 5374 7 mux
т
[
і - 4Э 0 L
J 1 7
60 a 0 ass 7 № —
Яі 8 1 0 [71 Ш 1
"зо 1
T2 0 583 60 12
112 0 0 a 3 7
"Is 1 3 1 1643 ' IS —
F 1832 0 0 52 3 4,1 ДЇ 21 0 1901561 105 ma*
Т
Т-4
46 1
* 0 1
10 і 8 0 1899 40 —
12 3 2 0 1
• 1
30 ГГ 11 0 583 40 96
144 4 0 0 3 5 1 7 42 ~ —
F 2040 26 0 0 2 і 2 0 4135 2 max
Г
Продолжение на следующей странице 588
Т-5
Х2 58 г 1 1 1 20 0 0 1241 20
хь 96 12 0 8 1
~Ъ 1 0 вдз 5
144 4 0 0 3
5 0 ] 742 і
F аоза 32 0 4 9
5 0 0 10С29
5 max
Т
Базисные перемен-ные Споболные переменные XI 14 ХЬ 0
14 8100 30 30 90 1 0 0 Й25[ 270
ЖЕ 9000 100 90 150 0 1 0 9341 90
хе Э500 т 50 10 0 0 1 2611 50
F 0 -70 -70 -60 0 0 0 -ЙЕЮ Шах
Т
Ті 6600 0 0 Б4 1 0 3
5 33 422 5 550
р=»
1
ifi 1000 0 -10 \ЇЩ 0 1 -2 41 Е9 400 13
XI so 1 ] 1
5 0 0 1
50 2611
50 250
F 3500 0 0 -4Q 0 0 . Г В JL7277 5 max
?4 52 200 13 0 34 13 0 [ 42
65 9 13 261 48S 65 4350 7
13 400 0 I 1 0 1 1 4119
13 13 130 <35 130
351 570 L щ\ 0 0 JL 3 14 012 475
ІЗ Ыи ' 650 130 335 її
F 63900 13 0 46
"із 0 0 23 63 0 13 319 338 65 max
Продолжение на следующей странице
Таблицы к задачей
Т-4
41 100 70 0 0 [ 7 6 41 040
11 11 и ГГ 1І
хз 375 5 0 1 0 1 3 П 603
11 6G J гзг 220 330
яг 475 65 1 0 0 і 1 745G
11 сю SG0 44 165
f 55 750 11 115 33 0 0 0 23 Й6 17 22 167 402
аз ҐПЙХ
Таблицы к задаче 3-
Базисные перемен-ный Свободные перрмеиные ЯП ЗГ4 ®a ? 0
x* 3740 60 30 30 1 0 0 1SGI 29
840 12 24 0 f 0 919 20
15 1260 42 :ss 18 0 0 1 1339 ?O
F 0 -GO —54 —І8 0 ] 0 0 -162 man
т
Х4 540 0 [Wj за
7 1 10
7 0 3837 7 42
30 t 2 7 4 7 0 1
42 0 919 70
16 420 0 6 -6 0 -1 1 420 70
F 1200 0 258 7 00 0 10
7 0 8056
7 max
Г
гэ 42 G 1 1
" 3 7
40 1
9 •i 127& 30 —
а 1 0 ГЇ]
III 1
45 1 І 8 0 37 10 12
J=6 ІЄ8 0 0 -4 7 15 1
" t 821 . fi —
F 2743 0 0 —26 43
TТі Й ~3 0 13 611 max
1
Продолжение но следующей апрпнице
590
Т-4
на 46 1
2 1 0 1
15 I 12 0 2849 СО —
гз IS 3
2 0 1 1
30 ' Г 12 0 291
Но" М4
10 216 6 0 0 а
5 0 1 1112
5 —
F 3QS0 39 0 0 2 I
"2 0 6201 10 ҐІПЗХ
Т
хз 58 3 ] 1 1
30 0 0 1861 30
144 18 0 12 2 5 1 0 373
&
96 216 С 0 0 3 0 1 1112
Ь
F 3132 48 0 6 9 5 0 0 15 939 . 5 max
Таблицы к задаче 4.
Базисные
mia Свободные П?рЄМЄЕЗМЬ(Є XI яа хз <4 хй ? 0
14 54 9 4 4 1 0 0 72 27/2
зга 63 9 5 5 0 і 0 83 63/5
їв 5 0 И 0 D 0 1 7 5
F 0 —9 —14 -5 0 0 0 -2а max
т
а* 34 0 0 4 1 0 44 9
Х5 38 9 0 5 0 1 -5 48 38
IT
яг 5 0 I 0 0 0 1 7 , —
F 70 -9 0 —5 0 0 14 70 пах
Г
Продолжение па следующей странице
Т-3
Ті 34 9 1 0 4 9 —
1
3 0 4
а 44
т 17 1
4 0 0 Т
1— -1 1 -1 А А
хг 5 0 1 0 0 0 J 7 —
F 104 0 0 -1 1 с 10 ] 14 ГТ1ЯЯ
Т
XI 2 ! 0 н 4 У 0 28 ? 13
Г.
4 О 0 1 -1 1 4 —
ав2 5 0 ! 0 0 0 1 7 —
F 103 0 0 0 0 1 9 118 fflM
Т
18 0 5 0 0 1 4
"В 0 38
S
«3 3S 0 5 0 1 0 1 5 АН Ь
5 0 1 0 0 0 1 7
F 108 0 0 0 0 1 э па max
Так как и индексной строке четвёртой симплексной таблицы опти-мального плана в столбце, содержащем x±t находится нуль, принадлежащий свободной переменной не входящей в Оазис, и а этом
столбце имеется не менее двух элементов — } из которых один
положительный, то задача, согласно замечанию 2, имеет множество оптимальных планов с одним и тем же значением целевой функции [F = 108). Выбираем столбец, содержащий за направляющий (за направляющую строку выбираем строку, в которой находится по-ложительный элемент рассматриваемого столбца). После заполнения
таблицы Т-5 получим план Хб = (О; 5; 0; q\ , он является
оптимальным, так как прнзнак оптимальности по индексной строке выполнен. Общий вид решения для нахождения всего множества оп-тимальных планов записывается в виде
* - аЛч + (1 - ^ 5; « (1 _ а); 0; о) ,
II М-метод. Вопрос о выборе базисе при решении задач линейного программирования является одним из основных. Рассмотрим один из методов нахождения базиса, который обычно называется методом ис-кусственного базиса или М-методом.
Задача- Найти максимум функции F — 12яі + 14х^ -Ь 16хз при условии
Х\ + Х2 -Ь ^ 30, Xi + 2х24 3хз ^г 51,
3xL + 2і;2 + Хз = 57> ^ J
xi ^ 0, xi ^ 0, хз ^ 0.
Эту задачу будем называть исходной.
Решение. I, Систему неравенств переводим в систему уравнений, введя неотрицательные дополнительные переменные
(7)
Xi -+¦ Xi -Ь ха + Х4 = 30, X! + 2х2 +Зяг3 "Хь = 51, Зхі + ~ 57,
xv ^ 0, f = 1,5.
JB первом уравнении имеется переменная х*, которую можно включить в базис, поэтому для получения базиса во второе и третье уравнения ВВОДИМ неотрицательные переменные (искусственные) SCG И #7 н получим так называемую расширенную задачу (М-задачу) по отношению к исходной
Ex + х2 -Н Хз + Х4 — 30, Xi 4- 2X2 + Зга - + XG 51» Зхі 4- 2x2 4 Гд + Х7 = S7, ^
> О, v ~ Т^Т.
и-
Введённые переменные включаем и целевую функцию с множителем ЛГ: F\ = F — М(хс + ху), если задача решается на максимум и Fi = F-ь М(хе + 27). задача решается на минимум, где М — некоторое достаточно большое число, конкретное значение которого обычно не задаётся.
Если система уравнений (7) не имеет переменной, которую можно включить в базис, то для получения базиса вводят три переменные.
Отметим, что переменные вводятся в те уравнения системы (7), в которых нет переменных, которые можно включить в базис.
Единичные вектора Л4, Ас, Я? образуют базис, так как определитель, составленный из компонент этих векторов (5), отличен от нуля. Вектора Aq И А7 И переменные х§ л х? называются искусственными. Теперь расширенная задача (М-задача) имеет мериый опорный план
= (0,0,0,30,0,51, 57) и она может быть решена симплекс-методом.
Пусть М- задач а имеет решение, тогда:
если в оптимальном плане расширенной задачи все искусственные переменные равны нулю (т.е. не являются базисными), то этот план является оптимальным планом исходной задачи;
если же в оптимальном плане расширенной задачи хотя бы одна искусственная переменная не равна нулю (т е, является базисной}, та исходная задача решения не имеет.
Если М-эадача не имеет оптимального решения, то и исходная задача неразрешима.
Составляем целевую функцию, исключив из неё базисные перемен-ные. Из (8) имеем
™ 51 - ті — 2х2 ~ Зїз + zs, = 57 — дхі - 2х2 — тз,
Т0ГАа хо + 2:7 = 108 - 4*і - 4X2 - 4z3 +
а целевая функция имеет вид Гі = F - М(хе + x7) =
= -108M 4- (12 + AM)x\ -Ь (14 AM)x2 + (1G+4M)?3 - Mx$,
Решаем расширенную задачу симплексным методом. Составляем таблицы,
В четвёртой таблице (Т-4) в индексной строке при больших М (Л/ ^ 2) нет отрицательных чисел, что свидетельствует о достижении оптимального плана М-задачи. При этом искусственные неизвестные в базис не йХодят. Следовательно, четвертую таблиц без столбцов яд и х? можно рассматривать как симплексную таблицу с оптимальным планом для задачи (7), при этом
F^ - F(X0 = 426, JT4 - (у! 0; f; О; И) , а для исходной задачи отсюда имеем
iw = F(Xj) = 426, - 0; Ц) .
ТІ
БЕ-
зяо
HUP
перс-
НЫС С&обші- нде дере-
HC-llliLJC XI ІЗ зез Х4 яз Xj Е в
хл 30 1 1 ] 1 0 0 0 34 30
re 51 1 2 a 0 1 0 57 17
XT 57 2 і 0 0 0 1 64 57
-lOSAf -14-Ш О м 0 0 -~Л2 — —119AtT max]
Г
Продолжение на следующей странице 594
Т-2
Xi ІЗ 2 з Г" 1 3 0 1 1 3 1
3 0 15 39 2
17 т
я 2 3 1 0 L 3 1
3 0 1» 51
17 to НІ 4
3 и 0 1
3 1
а І 45 Г5
Fx -4Ш-5- H 272 -до-дм 5 -1Q-4M " а 0 0 3 1В-ИМ
3 0 2G2- -43 М max
Т-3
it 3 0 0 0 1 гг
JL ] 4 1 15
т 12
¦ьэ 12 0 1 2 1 0 3 В 3 8 і
S 107 Є -
ЇЇ 15 1 1
а 0 0 1
fi 1
8 3 І 135 а 120
fi 372 0 0 0 0 9
2 Ьм 740/2 + +2М max
1
Т-4
xs 12 0 0 0 4 L "1 -і 15
яз 33 2 0 1 2 1 3 2 0 0 і І 19
її 27 2 і 1 2 0 1
2 0 0 і 2 15
А 426 0 0 0 13 0 л; М - 2 2М + + 442 max
Задание. В задаче найти максимум функции F — 4- 2x2 + Зхз гтрн условии
' + 2^2 + Зі3 = IB, 2^1 Ч- 5тя ^ 20, 1 + 2x2 - ^ 10, ( xv^0, is = ТД
Проверить вычислен НЯн
Решение. Решаем расширенную задачу: найти максимум функции
Fi = -28М + (1 + 2M)xi + (2 + Ш)хг + (3 + 2М)х3 - Мхъ
595
536
(Гл. X
гри условии , + ^ + ^ + ^ = 1е
<
+ + + 34 = 20, а?і + — - -i-%7 = 10»
У = Tj.
Так как = 18 — — ~ Зхз, а = 10 Ti ~ + + а;3, то х6 + х7 = 28 - 2xi - - 2х3 +
Строим таблицы.
Базис-ные пере-менные Свобод-
HL1E
пере-менный ЇЙ лтд їй Хв ¦
St І: 0
XQ 1Й ] 2 3 0 1 0 2& D
3=4 20 2 1 Ь 1 0 0 Q '29 20
Х7 to 1 в -І 0 -1 0 1 12 5
А -2Ш —
— 2 А/ —2 — — 4М - 2М 0 м 0 0 —G - - 35 М та*
Т-2
а 0 0 Щ 0 I 1 13 2
?4 15 3 2 0 11
2 1 1
і 0 1 ~2 23 ЗО
ТІ
Хї 5 і 2 1 t 2 0 1
2 0 1
а fi —
Л 10 - -SM ¦ 0 0 -4 - 0 -
-Л/ 0 + Ш — 1 їм гг.аи
Т-3
; этэ 2 О О 1 0 1 4 1 4 і 4 13
Т
І TJ
і 4 3 2 0 0 ] 7
11 т 7
41
т
1 Б 1 2 1 0 0 3 а 1 в * 3 8 61 а
IS 0 0 0 0 0 Ц-ЛГ М 2М + + 19 шах
Ответ исходной задачи: Fraa3C = Fi№) = 18, Х2 = (0; 6; 2).
59б