ЛП-метод-каЛуценко
.pdfтельно, первый столбец будет генеральным. Найдем теперь отношения свободных чле-
нов к положительным элементам генерального столбца: ( ; |
20 |
5; |
28 |
9,33...) . |
|
4 |
3 |
||||
|
|
|
Наименьшее из этих отношений оказалось во второй строке. Пометим генеральный элемент символом *.
Переменную x1 введем вместо x5 в число базисных. На месте генерального элемента p* 4 запишем число 1, вместо остальных элементов генерального столбца за-
пишем нули, все остальные элементы генеральной строки поделим на генеральный элемент, число 4. В результате мы получим таблицу 4.
Заполним клетку помеченную символом ( ). Соответствующие элементы генеральной строки и столбца будут равны: q 20 , r 7 , поэтому в этой клетке следует
написать 0 |
20 |
7 |
35 ( по формуле 13). В клетке, помеченной знаком ( ), напишем |
||||
|
|
|
|
||||
|
|
4 |
|
||||
|
|
|
|
|
|
|
|
0 |
( 5) 1 |
5 |
. Аналогично заполняются оставшиеся клетки Таблицы 4. (Таблица 5.) |
||||
4 |
|
|
4 |
||||
|
|
|
|
|
Таблица 5.
|
x1 |
x2 |
x3 |
x4 |
x5 |
b |
x3 |
0 |
9/4 |
1 |
5/4 |
0 |
55 |
x1 |
1 |
–3/4 |
0 |
1/4 |
0 |
5 |
x5 |
0 |
13/4* |
0 |
-3/4 |
1 |
13 |
F1 |
0 |
29/4 |
0 |
-7/4 |
0 |
-35 |
Таблица 6.
|
x1 |
x2 |
x3 |
x4 |
x5 |
b |
x3 |
0 |
0 |
1 |
23/13 |
-9/13 |
46 |
x1 |
1 |
0 |
0 |
1/13 |
3/13 |
8 |
x2 |
0 |
1 |
0 |
-3/13 |
4/13 |
4 |
F1 |
0 |
0 |
0 |
-1/13 |
-29/13 |
-64 |
Таблица 5 порождает следующее базисное решение задачи:
x1 5 , x2 0 , x3 55 , x4 0 , x5 13 .
Значение целевой функции будет F1 35 . То есть на новом базисном плане оно
меньше на 35 единиц, чем на первоначальном.
Найденное нами базисное решение не оптимально, так как в последней строке Таблицы 5 есть положительные элементы. Для нахождения следующего базисного плана выберем базисный столбец симплекс-таблицы 5. Так как в последней строке поло-
жительный элемент только один, то за такой столбец следует взять столбец x2 .
|
Как и ранее вычислим отношения свободных членов к положительным элементам |
||||||||||
генерального |
столбца. |
У |
нас |
получатся |
следующие |
отношения: |
|||||
(55 : |
9 |
24,4..; |
;13 : |
13 |
|
4) . Наименьшим из этих отношений оказалось третье и, |
|||||
|
|
|
|||||||||
|
4 |
|
4 |
|
|
|
|
|
|
следовательно, генеральной строкой будет третья строка. Таким образом, генеральным
13
элементом таблицы 5 будет число 4 .
Выполним преобразование таблицы 5 и составим таблицу 6. Составление этой таблицы удобно начинать с последней строки, так как именно по ней определяется оптимальность получаемого решения. Так как все элементы последней строки оказались отрицательными, то порождаемое этой таблицей базисное решение
x1 8 , x2 4 , x3 46 , x4 0 , x5 0
будет оптимальным, а минимальное значение целевой функции F1,min 64 .
11
Построение допустимого плана с помощью искусственного базиса
Как мы уже отмечали, преобразования симплекс метода могут выполняться только с базисного допустимого решения. Однако поиск такого решения также довольно непрост. Формально мы должны перебирать базисные решения до тех пор пока мы не найдем неотрицательное или не покажем что таких не существует.
В этом параграфе мы покажем, как симплекс-методом можно найти базисное допустимое решение или доказать, что система ограничений канонической задачи несовместна.
Предположим, что в системе уравнений (12) значения свободных членов отрицательны. Умножим эти уравнения на –1 и составим новую систему уравнений:
a1,1x1 |
a1,2 x2 |
x3 |
y1 |
b1, |
|
a2,1x1 |
a2,2 x2 |
x4 |
y2 |
b2 , |
(14) |
a3,1x1 |
a3,2 x2 |
x5 |
y3 |
b3. |
|
В этой системе искусственные переменные y1 , y2 , y3 можно взять за базисные, тогда все компоненты базисного решения y1 b1 , y2 b2 , y3 b3 будет неотри-
цательны.
Составим новую задачу:
f y1 |
y2 |
y3 |
min |
при ограничениях (14) и x1 , x2 , x3 , x4 , x5 , y1 , y2 , y3 |
0 . |
Наименьшее возможное значение вспомогательной целевой функции f |
равно |
||||
нулю и |
оно |
достигается |
только в том случае, когда значения всех переменных |
y1 , y2 , y3 равны нулю и они выведены из числа базисных. Таким образом, среди ба-
зисных переменных будут только иксы, а значит, был построен базисный допустимый план, и в дальнейшем переменные игреки можно не рассматривать.
Если же минимальное значение вспомогательной функции f положительно, то
система (12) не имеет базисного решения с неотрицательными компонентами.
Пример 8. Решить следующую задачу линейного программирования симплекс методом.
F |
2x1 |
3x2 |
min |
|
(15) |
при ограничениях |
|
|
|
|
|
|
x1 |
3x2 |
30, |
|
|
|
2x1 |
x2 |
20, |
x1, x2 0 . |
(16) |
|
5x1 |
4x2 |
20, |
|
|
Решение. Введем дополнительные переменные |
|
|
|||
x3 |
30 (x1 |
3x2 ) 0, |
|
||
x4 |
20 |
(2x1 |
x2 ) |
0, |
|
x5 |
20 ( 5x1 4x2 ) 0, |
|
и перейдем к канонической задаче линейного программирования.
F |
2x1 3x2 |
min , |
(17) |
при ограничениях
12
x1 |
3x2 |
x3 |
30, |
|
2x1 |
x2 |
x4 |
20, |
(18) |
5x1 |
4x2 |
x5 |
20, |
|
x1 , x2 , x3 , x4 , x5 0 .
Если в этой задаче переменные x3 , x4 , x5 взять за базисные, а x1 , x2 |
за свобод- |
ные, то базисным решением системы уравнений будет набор: (0, 0, 30, 20, |
20) , пя- |
тая компонента которого отрицательна. То есть это решение будет недопустимым. Следовательно, за базисные мы должны взять какие-то другие переменные.
Введем искусственную переменную y1 |
в третье уравнение: |
|||
5x1 |
4x2 |
x5 |
y1 |
20 |
и составим вспомогательную целевую функцию: |
|
|
||
f y1 |
20 (5x1 |
4x2 |
x5 ) , |
в записи которой базисная переменная y1 выражена через свободные. Составим вспо-
могательную задачу.
f 20 (5x1 4x2 x5 ) min
при ограничениях
|
x1 |
3x2 |
x3 |
30, |
|
2x1 |
x2 |
x4 |
20, |
5x1 |
4x2 |
x5 |
y1 |
20, |
x1 , x2 , x3 , x4 , x5 , y1 |
0 . |
|||
Для этой задачи составим симплекс-таблицу 7. В эту таблицу мы включили пер- |
||||
воначальную целевую функцию F |
0 |
(2x1 |
3x2 ) , которая будет преобразовывать- |
|
ся по тем же правилам, что и вся симплекс-таблица. |
|
|||
Таблица 7. |
|
|
Таблица 8. |
|
x1 |
x2 |
x3 |
x4 |
x5 |
y1 |
b |
x3 |
1 |
3 |
1 |
0 |
0 |
0 |
30 |
x4 |
2 |
1 |
0 |
1 |
0 |
0 |
20 |
y1 |
5* |
4 |
0 |
0 |
-1 |
1 |
20 |
F |
2 |
3 |
0 |
0 |
0 |
0 |
0 |
f |
5 |
4 |
0 |
0 |
-1 |
0 |
20 |
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
y1 |
b |
x3 |
0 |
11/5 |
1 |
0 |
1/5 |
-1/5 |
26 |
x5 |
0 |
-3/5 |
0 |
1 |
2/5 |
-2/5 |
12 |
x1 |
1 |
4/5 |
0 |
0 |
-1/5 |
1/5 |
4 |
F |
0 |
7/5 |
0 |
0 |
2/5 |
-2/5 |
-8 |
f |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
|
|
|
|
|
|
|
За генеральный столбец в таблице 7 мы возьмем столбец |
x1 . Отношения свобод- |
ных членов к элементам этого столбца будут |
соответственно равны |
(30 /1; 20 / 2; 20 / 5) . Поэтому генеральный элемент будет в третьей строчке и равен 5. После преобразований у нас получиться таблица 8.
Переменная x1 вошла в число базисных вместо переменной y1 , а минимальное
значение вспомогательной функции |
f равно нулю. |
Следовательно, нами построено |
базисное допустимое решение канонической задачи (17, 18): |
||
x1 4 , x2 |
0 , x3 26 , x4 |
0 , x5 12 . |
13
Заметим, что значение целевой функции F на этом решение равно –8. Симплекс таблица для первоначальной задачи получается из таблицы 8 вычеркиванием столбца y1 и последней строки f . У нас получиться симплекс-таблица 9.
Таблица 9. Таблица 10.
|
x1 |
x2 |
x3 |
x4 |
x5 |
b |
x3 |
0 |
11/5 |
1 |
0 |
1/5 |
26 |
x4 |
0 |
-3/5 |
0 |
1 |
2/5* |
12 |
x1 |
1 |
4/5 |
0 |
0 |
-1/5 |
4 |
F |
0 |
7/5 |
0 |
0 |
2/5 |
-8 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
b |
x3 |
0 |
5/2* |
1 |
-1/2 |
0 |
20 |
x5 |
0 |
-3/2 |
0 |
5/2 |
1 |
30 |
x1 |
1 |
1/2 |
0 |
1/2 |
0 |
10 |
F |
0 |
2 |
0 |
-1 |
0 |
-20 |
В этой таблице выберем генеральный элемент и выполним преобразование таблицы. У нас получиться Таблица 10. В этой таблице значение целевой функции F равно –20, что меньше чем в таблице 9. Снова применим алгоритм симплекс метода. У нас получится Таблица 11.
Таблица 11.
|
x1 |
x2 |
x3 |
x4 |
x5 |
b |
x2 |
0 |
1 |
|
|
0 |
8 |
x5 |
0 |
0 |
|
|
1 |
18 |
x1 |
1 |
0 |
|
|
0 |
6 |
F |
0 |
0 |
-4/5 |
-3/5 |
0 |
-36 |
Все элементы последней строки отрицательны. Следовательно эта таблица порождает оптимальное базисное решение задачи (17, 18). А именно,
x1 6 , x2 |
8 , x3 0 , x4 0 , x5 18 . |
При этом минимальное значение функции равно –36. |
|
Минимальное значение функции F задачи (25, 16) равно также –36 и оно дости- |
|
гается в точке с координатами x1 6 , |
x2 8 . |
Двойственная задача и теорема двойственности
Определение 9. Следующая задача называется двойственной к задаче (1,2).
Задача 3. Найти
G bt y |
min , |
|
|
|
|
|
|
|
(19) |
||
At y |
c , y |
0 , |
|
|
|
|
|
|
|
(20) |
|
где матрицы A, b,c определяются по формулам (3), а yt |
|
( y , y |
2 |
, y |
m |
) . |
|||||
|
|
|
|
|
|
|
1 |
|
|
||
В развернутой форме эта стандартная задача линейного программирования |
|||||||||||
может быть записана в следующем виде. |
|
|
|
|
|
|
|
|
|
||
Задача 3’. Найти минимум линейной функции |
|
|
|
|
|
|
|
||||
G bt y |
b y |
b y |
2 |
b |
y |
m |
, |
|
|
|
(19 ) |
|
1 1 |
2 |
m |
|
|
|
|
|
|
при ограничениях:
14
a1,1 y1 |
a2,1 y2 |
am,1 ym |
c1 , |
a1,2 y1 |
a2,2 y2 |
am,2 ym |
c2 , |
|
|
(20 ) |
|
|
|
||
a1,n y1 |
a2,n y2 |
am,n ym |
cn , |
|
|
y1, y2 , ym 0 . |
|
Задачи (1, 2) и (91, 92) называются взаимно двойственными задачами, а задача (1, 2) по отношению к задаче (91, 92) называется прямой.
Пример 9. Составить двойственные задачи к следующим задачам.
a) F |
7x1 |
2x2 |
max , |
b) F |
2x1 |
3x2 |
min , |
5x1 |
6x2 |
30, |
|
x1 |
3x2 |
30, |
|
4x1 |
3x2 |
20, |
x1, x2 0 . |
2x1 |
x2 |
20, |
x1, x2 0 . |
3x1 |
x2 |
28, |
|
5x1 |
4x2 |
20, |
|
Решение. a) Число переменных в двойственной задаче совпадает с числом ограничений прямой задачи и равно 3. Обозначим их через y1 , y2 , y3 . Так как в прямой за-
даче требуется найти максимум, то знаки неравенств во всех ограничениях должны быть « ». Коэффициенты целевой функции двойственной задачи совпадают со свободными частями неравенств, а правые части неравенств двойственной задачи совпадают с коэффициентами целевой функции прямой задачи. В итоге мы получаем следующую задачу линейного программирования.
G 30 y1 20 y2 28 y3 min ,
5y1 4 y2 |
|
3y3 |
7, |
|
|
|
|
6 y 3y |
2 |
y |
3 |
2, y1 |
, y2 |
, y3 |
0 . |
1 |
|
|
|
|
|
||
b) Прежде чем составить двойственную задачу следует прямую задачу преобразо- |
вать так, чтобы все неравенства в ней имели вид « |
». Для этого мы умножим первые |
|||
два неравенства на –1. После этого мы уже сможем записать двойственную задачу. |
|
|||
G |
30 y1 20 y2 |
20 y3 |
max , |
(21) |
y1 |
2y2 |
5y3 |
2, |
y1 |
, y2 |
, y3 |
0 . |
(22) |
|
3y1 |
y2 |
4y3 |
3, |
||||||
|
|
|
|
|
Для решения двойственной задачи можно применить те же методы решения, как и для прямой задачи: составление канонической задачи, поиск допустимого базисного плана, преобразование таблиц. Однако, всего этого можно избежать, если есть базисное решение прямой задачи. Базисное решение двойственной задачи можно взять из строки для целевой функции прямой задачи. А для проверки оптимальности полученного решения можно воспользоваться теоремой двойственности.
Теорема двойственности. Пусть и допустимые решения задач и соответствен-
но, тогда |
|
1. |
G( y) F (x) . |
2. |
Если G( y) F (x) , то x, y – оптимальные решения соответствую- |
|
щих задач. |
15
Рассмотрим следующий пример решения двойственной задачи и проверки его по теореме двойственности.
Пример 10. Найти решение двойственной задачи к задаче примера 8 и проверить его по теореме двойственности.
Решение. Двойственной задачей к задаче (15, 16) будет задача (21, 22). Итоговой таблицей прямой задачи будет таблица 11. Меняя знаки у чисел стоящей в последней строчке, мы укажем значения переменных двойственной задачи.
y1 4 / 5 , y2 3 / 5 , y3 0 |
(23) |
Проверим теперь допустимость полученного решения. Для этого подставим их в неравенства системы (22). Мы получим
4 |
2 |
3 |
0 2 , |
3 |
4 |
|
3 |
0 3. |
|
5 |
5 |
5 |
5 |
||||||
|
|
|
|
Следовательно, план (4 / 5; 3/ 5; 0) является допустимым для задачи (15, 16). Вычислим теперь значение целевой функции на этом плане. У нас получиться:
G( y) 30 54 20 53 0 36.
Это значение совпадает с сосчитанным ранее значением целевой функции прямой задачи. А поэтому приведенный нами план двойственной задачи (23) будет оптимальным.
Пример решения задачи
Задача 4. Найти максимум линейной функции F 4x1 3x2 , если переменные x1 , x2 удовлетворяют следующей системе ограничений:
x1 |
4x2 |
12, |
3x1 |
2x2 |
26, x1, x2 0 . |
x1 |
2x2 |
10, |
В математических символах эта задача имеет следующий вид:
|
max( 4x1 |
3x2 ) , |
|
x1 |
4x2 |
12, |
|
3x1 |
2x2 |
26, |
x1, x2 0 . |
x1 |
2x2 |
10, |
|
1. Запишем эту задачу в матричной форме. Для этого умножим первое и третье неравенство системы на –1. У нас получиться следующая система неравенств:
x1 4x2 12, 3x1 2x2 26,
x1 2x2 10.
Следовательно, наша задача в матричной форме примет вид:
F ct x max ,
Ax b , x 0,
где
16
|
|
|
1 |
4 |
|
12 |
|
4 |
|
x1 |
|
|
|
|
|
|
|
A |
3 |
2 |
; b |
26 |
; c |
; x |
|
|
|
(24) |
|||
|
|
3 |
x2 |
|
|
|
|||||||||
|
|
|
1 |
2 |
|
10 |
|
|
|
|
|
|
|
|
|
2. |
Для построения |
канонической |
задачи |
введем |
дополнительные |
переменные |
|||||||||
x3 , x4 , x5 и запишем систему ограничений задачи в виде |
|
|
|
|
|
|
|
||||||||
|
|
|
x1 |
4x2 |
x3 |
12, |
|
|
|
|
|
|
|
|
|
|
|
3x1 |
2x2 |
x4 |
26, |
x1 , x2 , x3 , x4 , x5 |
0 . |
|
|
|
|||||
|
|
|
x1 |
2x2 |
x5 |
10, |
|
|
|
|
|
|
|
|
|
Окончательно, каноническая задача линейного программирования для нашей за- |
|||||||||||||||
дачи имеет вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F1 |
F |
4x1 |
3x2 |
min, |
при ограничениях |
|
|
|
|||||
|
|
x1 |
4x2 |
x3 |
12, |
|
|
|
|
|
|
|
|
|
|
|
|
3x1 |
2x2 |
x4 |
26, |
x1 , x2 , x3 , x4 , x5 |
0 . |
|
|
|
(25) |
||||
|
|
x1 |
2x2 |
x5 |
10, |
|
|
|
|
|
|
|
|
|
|
3. |
Для того чтобы решить начальную задачу геометрически, построим прямые |
||||||||||||||
|
|
|
|
|
|
(III) |
|
|
|
x1 |
4x2 |
12 , |
|
(I ) ; |
|
x2 |
|
|
|
|
|
|
|
|
3x1 |
2x2 |
26 , |
(II ) ; |
|||
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
Q(4,7) |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
x1 |
2x2 |
|
10 , |
(III ) ,. |
|||
|
|
|
|
|
|
|
|
|
|
|
|||||
7 |
|
|
|
|
|
|
|
|
|
и отметим |
стрелочками |
||||
|
|
|
|
|
|
|
|
|
|
те полуплоскости, в кото- |
|||||
|
|
|
|
|
|
|
|
|
|
рых |
выполняются соот- |
||||
5 |
|
|
|
|
|
|
|
|
|
ветствующие |
неравен- |
||||
|
|
|
D |
|
|
|
|
|
|
ства. |
Областью допусти- |
||||
|
|
|
|
|
|
|
|
|
мых решений задачи ока- |
||||||
|
|
|
|
|
|
|
|
|
|
||||||
3 |
|
|
|
|
|
|
|
|
|
зался четырехугольник. |
|||||
|
|
|
|
|
|
|
|
|
|
Построим |
|
прямую |
|||
(I) |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
L: 4x1 |
3x2 |
12 и бу- |
||||
|
|
|
|
|
|
|
|
|
|
||||||
1 |
|
|
|
|
|
|
|
|
|
дем ее передвигать в на- |
|||||
|
|
|
|
|
|
|
|
|
x1 |
правлении |
|
|
вектора |
||
|
|
|
|
|
|
|
|
|
n(4,3) . Свое максималь- |
||||||
|
|
|
|
|
|
|
|
|
|
||||||
-1 |
1 |
3 |
|
5 |
|
7 |
|
9 |
|
ное значение на множест- |
|||||
|
|
L |
|
|
|
(II) |
|
|
|||||||
|
|
|
|
|
|
|
|
ве D функция |
F примет |
||||||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
в точке Q . Найдем ее ко- |
|||||
ординаты. Для этого решим систему уравнений: |
3x1 |
2x2 |
26 , x1 |
2x2 |
|
|
10 . |
||||||||
Функция |
F принимает свое максимальное на множестве |
D значение равное |
|||||||||||||
Fmax |
37 в точке с координатами x1 |
4 ; x2 |
7 . |
|
|
|
|
|
|
|
|
||||
4. Если за базисные переменные канонической задачи (25) взять переменные |
|||||||||||||||
x3 , x4 , x5 , то соответствующий базисный план будет недопустим. Для построения на- |
|||||||||||||||
чального плана введем искусственную переменную |
y1 |
и составим вспомогательную |
|||||||||||||
задачу. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
f |
|
y1 12 (x1 |
4x2 |
x3 ) |
min , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
x1 |
|
4x2 |
x3 |
y1 |
12, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
3x1 |
2x2 |
x4 |
26, |
x1 , x2 , x3 , x4 , x5 , y1 |
0 . |
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
x1 |
2x2 |
x5 |
10, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Составим симплекс-таблицу и применим симплекс метод. В таблицы включена |
|||||||||||||||||||||||||||||
также функция F1 , а генеральные строки и столбцы таблиц заштрихованы. |
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
x1 |
|
|
|
x2 |
|
|
x3 |
|
x4 |
|
x5 |
|
y1 |
|
b |
|
|
b / x2 |
|||||||
|
y1 |
|
1 |
|
|
|
4* |
|
|
-1 |
|
|
0 |
|
|
0 |
|
|
1 |
|
|
12 |
|
|
|
12/4 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
x4 |
3 |
|
|
|
2 |
|
|
0 |
|
1 |
|
0 |
|
0 |
|
26 |
|
|
|
– |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
x5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
-1 |
|
|
|
2 |
|
|
0 |
|
0 |
|
1 |
|
0 |
|
10 |
|
10/2 |
|
|
|||||||||||
|
F1 |
4 |
|
|
|
3 |
|
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
f |
1 |
|
|
|
4 |
|
|
-1 |
|
0 |
|
0 |
|
0 |
|
12 |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
1/4 |
|
|
1 |
|
– 1/4 |
0 |
|
0 |
|
1/4 |
|
3 |
|
|
|
|
|
|
||||||||||
|
x4 |
5/2 |
|
|
0 |
|
|
1/2 |
|
1 |
|
0 |
|
|
– 1/2 |
20 |
|
|
|
|
|
|
||||||||
|
x5 |
-3/2 |
|
|
0 |
|
|
1/2 |
|
0 |
|
1 |
|
|
– 1/2 |
4 |
|
|
|
|
|
|
||||||||
|
F1 |
|
13/4 |
|
|
0 |
|
|
3/4 |
|
0 |
|
0 |
|
|
– 3/4 |
-9 |
|
|
|
|
|
|
|||||||
|
f |
|
0 |
|
|
|
0 |
|
|
0 |
|
0 |
|
0 |
|
|
– 1 |
0 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Из этой таблицы мы находим допустимый базисный план канонической задачи: |
|||||||||||||||||||||||||||||
|
x1 |
|
0 , x2 |
3 , x3 |
0 , x4 |
20 , x5 5 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
5. Исключим теперь из таблицы вспомогательную функцию |
|
f , искусственную |
|||||||||||||||||||||||||||
переменную y1 |
и решим полученную задачу симплекс методом. |
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
x1 |
|
|
|
x2 |
|
|
x3 |
|
x4 |
|
x5 |
|
b |
|
b / x2 |
|
|
|
|
|
|||||
|
x2 |
1/4 |
|
|
1 |
|
– 1/4 |
|
0 |
|
0 |
|
3 |
|
|
– |
|
|
|
|
|
|||||||||
|
x4 |
5/2 |
|
|
0 |
|
|
1/2 |
|
1 |
|
0 |
|
20 |
|
40 |
|
|
|
|
|
|
||||||||
|
x5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
– 3/2 |
|
|
0 |
|
|
1/2* |
|
|
0 |
|
|
1 |
|
|
4 |
|
|
8 |
|
|
|
|
|
|
||
|
F1 |
|
13/4 |
|
|
0 |
|
|
3/4 |
|
0 |
|
0 |
|
-9 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
x2 |
|
– 1/2 |
|
|
1 |
|
|
0 |
|
0 |
|
1/2 |
|
5 |
|
|
– |
|
|
|
|
|
|||||||
|
x4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
4* |
|
|
|
0 |
|
|
0 |
|
|
1 |
|
|
–1 |
|
|
16 |
|
|
4 |
|
|
|
|
|
|
|
|
x3 |
|
– 3 |
|
|
0 |
|
|
1 |
|
0 |
|
2 |
|
8 |
|
|
– |
|
|
|
|
|
|||||||
|
F1 |
|
|
11/2 |
|
|
0 |
|
|
0 |
|
0 |
|
|
– 3/2 |
|
–15 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
x2 |
0 |
|
|
|
1 |
|
|
0 |
|
1/8 |
|
3/8 |
|
7 |
|
|
|
|
|
|
|
|
|
||||||
|
x1 |
1 |
|
|
|
0 |
|
|
0 |
|
1/4 |
|
|
– 1/4 |
4 |
|
|
|
|
|
|
|
|
|
||||||
|
x3 |
0 |
|
|
|
0 |
|
|
1 |
|
3/4 |
|
11/4 |
|
20 |
|
|
|
|
|
|
|
|
|
||||||
|
F1 |
|
0 |
|
|
|
0 |
|
|
0 |
|
|
–11/8 |
|
– 1/8 |
-37 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18
Из последней таблицы мы получим оптимальное решение канонической задачи
(25): |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F1,min |
37, |
x1 |
4 , |
x2 |
7 , |
x3 |
20 , |
x4 |
0 , x5 |
0 , |
|||||
а следовательно функция F принимает свое максимальное на множестве D значение |
|||||||||||||||
равное Fmax |
37 в точке с координатами x1 |
4 ; |
x2 |
7 . |
|
||||||||||
6. Двойственная задача к искомой задаче будет иметь вид: |
|||||||||||||||
|
|
|
|
|
|
G |
|
12 y1 |
26 y2 |
10 y3 |
min , |
||||
|
|
|
|
|
|
|
y1 |
3y2 |
y3 |
|
4, |
y1 , y2 |
, y3 |
0 , |
|
|
|
|
|
|
|
4y1 |
2y2 |
2y3 |
|
3, |
|||||
|
|
|
|
|
|
|
|
|
|
||||||
или в матричной форме: |
F |
ct y |
min , |
At y |
c , y |
0 с матрицами (24) и матри- |
|||||||||
цей yt ( y , y |
2 |
, y |
3 |
) . |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
7. Из последней симплекс таблицы мы найдем значения двойственных перемен- |
|||||||||||||||
ных: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
0 , y2 |
11 / 8 , y3 |
1/ 8 |
Подставим эти числа в ограничения двойственной задачи и целевую функцию:
0 3 |
11 1 |
4 , 0 2 |
11 |
2 |
1 |
3, G 0 26 |
11 |
10 |
1 |
37. |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
8 |
|
8 |
|
8 |
|
8 |
8 |
|
8 |
||||||||
|
|
|
|
|
|
|
|
Так как выполнены все условия теоремы двойственности, то найденное решение:
Gmin 37 , y1 0 , y2 11 / 8 , y3 1/ 8
будет оптимальным решением двойственной задачи.
Варианты заданий
1 |
max( 5x1 |
6x2 ) |
2 |
|
max( x1 |
3x2 ) , |
3 |
|
max( x1 |
2x2 ) , |
4 |
|
max( 2x1 |
|
x2 ) , |
||||
|
|
|
|
|
|
||||||||||||||
|
2x1 |
x2 |
2, |
|
|
x1 |
x2 |
1, |
|
|
2x1 |
3x2 |
6, |
|
|
3x1 |
5x2 |
15, |
|
|
4x1 |
6x2 |
17, |
|
|
x1 |
x2 |
5, |
|
|
3x1 |
2x2 |
12, |
|
|
x1 |
x2 |
6, |
|
|
3x1 |
4x2 |
12, |
|
|
4x1 |
x2 |
8, |
|
|
x1 |
2x2 |
8, |
|
|
3x1 |
2x2 |
6, |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
||||
|
max( 3x1 |
x2 ) , |
|
|
max( 2x1 |
5x2 ) , |
|
|
max( x1 |
2x2 ) , |
|
|
max( 2x1 |
|
x2 ) , |
||||
5 |
6 |
|
7 |
|
8 |
|
|
||||||||||||
|
|
|
|
|
|
||||||||||||||
|
2x1 |
6x2 |
12, |
|
|
x1 |
2x2 |
6, |
|
|
x1 |
2x2 |
10, |
|
4x1 |
3x2 |
|
12, |
|
|
x1 |
x2 |
1, |
|
|
x1 |
x2 |
1, |
|
|
x1 |
x2 |
2, |
|
|
x1 |
2x2 |
|
8, |
|
x1 |
x2 |
1, |
|
|
|
x1 |
1, |
|
|
x1 |
4x2 |
4, |
|
|
2x1 |
x2 |
10, |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
||||
|
min( x1 |
2x2 ) , |
|
min( |
2x1 |
3x2 ) , |
|
|
min( x1 |
x2 ) , |
|
|
min( 5x1 |
|
2x2 ) |
||||
9 |
10 |
11 |
|
12 |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||
|
x1 |
x2 |
1, |
|
|
x1 |
x2 |
5, |
|
|
x1 |
x2 |
1, |
|
2x1 |
6x2 |
|
12, |
|
|
2x1 |
3x2 |
6, |
|
|
x1 |
4x2 |
4, |
|
|
x1 |
x2 |
7, |
|
|
x1 |
x2 |
|
1, |
|
|
x1 |
8, |
|
|
x1 |
x2 |
3, |
|
|
x1 |
2x2 |
2, |
|
|
x1 |
x2 |
1, |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
|
x1, x2 |
0 |
|
19
13 |
|
|
min( 2x1 |
5x2 ) , |
14 |
|
|
max( 2x1 |
x2 ) , |
15 |
|
max( |
x1 |
|
2x2 ) , |
16 |
|
min( 2x1 |
|
3x2 ) , |
||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
2x1 |
6x2 |
12, |
|
|
|
x1 |
4x2 |
|
4, |
|
|
x1 |
x2 |
|
4, |
|
|
x1 |
x2 |
|
1, |
||
|
|
|
x1 |
x2 |
1, |
|
|
x1 4x2 |
12, |
|
|
x1 |
x2 |
2, |
|
|
x1 |
x2 |
|
3, |
||||
|
|
|
x1 |
2x2 |
2, |
|
|
|
x1 |
2x2 |
|
2, |
|
|
2x1 |
x2 |
|
8, |
|
|
2x1 |
x2 |
|
6, |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|||||
|
max( 5x1 |
3x2 ) , |
|
|
|
max( x1 |
|
3x2 ) , |
|
|
max( 2x1 |
|
x2 ) , |
|
|
max( x1 |
|
4x2 ) |
||||||
17 |
18 |
|
|
|
19 |
|
|
20 |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
3x1 |
2x2 |
12, |
|
|
|
x1 |
x2 |
|
3, |
|
|
x1 |
x2 |
|
4, |
|
|
x1 |
x2 |
|
1, |
||
|
|
|
x1 |
2x2 |
0, |
|
7x1 |
6x2 |
|
42, |
|
|
|
x1 |
|
3, |
|
|
|
x2 |
|
3, |
||
|
|
|
|
x1 |
8, |
|
|
|
|
x1 |
|
2, |
|
|
x1 |
x2 |
|
1, |
|
|
x1 |
2x2 |
|
13, |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|||||
|
|
|
max( 2x1 |
5x2 ) |
|
|
|
max( x1 |
|
4x2 ) , |
|
|
max( x1 |
3x2 ) , |
|
|
max( 2x1 |
x2 ) , |
||||||
21 |
|
|
22 |
|
|
|
23 |
|
24 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
x1 |
x2 |
2, |
|
|
|
x1 |
2x2 |
|
6, |
|
|
x1 |
x2 |
4, |
|
|
3x1 |
2x2 |
|
4, |
|
|
7x1 |
3x2 |
14, |
|
|
|
x1 |
2x2 |
2, |
|
|
2x1 |
x2 |
5, |
|
|
x1 |
3x2 |
|
5, |
||||
|
|
|
3x1 |
x2 |
6, |
|
|
|
x1 |
6x2 |
|
6, |
|
|
x1 |
2x2 |
5, |
|
|
4x1 |
x2 |
|
20, |
|
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|||||
|
|
|
max( 2x1 |
7x2 ) |
|
|
min( |
x1 |
|
2x2 ) , |
|
|
min( |
2x1 |
|
3x2 ) , |
|
|
max( 2x1 |
|
3x2 ) |
|||
25 |
|
|
26 |
|
27 |
|
|
28 |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
x1 |
x2 |
4, |
|
|
|
x1 |
x2 |
|
0, |
|
|
4x1 |
3x2 |
|
12, |
|
|
x1 |
2x2 |
|
6, |
|
|
|
x1 5, |
|
|
|
x1 |
x2 |
8, |
|
|
x1 |
6x2 |
|
24, |
|
|
x1 |
x2 |
|
2, |
|||
|
|
|
x1 |
x2 |
8, |
|
|
3x1 |
x2 |
12, |
|
|
5x1 |
3x2 |
|
15, |
|
|
2x1 |
x2 |
|
6, |
||
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|||||
|
|
|
max( x1 |
x2 ) , |
|
|
|
max( x1 |
|
4x2 ) , |
|
|
min( x1 |
x2 ) , |
|
|
max( 4x1 |
x2 ) , |
||||||
29 |
|
|
30 |
|
|
|
31 |
|
32 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
3x1 |
2x2 |
3, |
|
5x1 |
4x2 |
|
20, |
|
|
x1 |
x2 |
|
2, |
|
2x1 |
3x2 |
|
12, |
|||
|
|
|
x1 |
3x2 |
3, |
|
|
|
2x1 |
x2 |
|
2, |
|
|
x1 |
3x2 |
|
3, |
|
|
2x1 |
x2 |
2, |
|
|
5x1 |
8x2 |
40, |
|
|
|
x1 |
2x2 |
|
2, |
|
5x1 |
8x2 |
|
40, |
|
|
x1 |
2x2 |
|
2, |
|||
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
|
|
|
x1, x2 |
0 |
Литература
1.Ашманов С.А. Линейное программирование, М., Наука, 1981, 340с.
2.Галанова З.С., Родин В.И., Ермошин А.А., Конова С.Ю. Линейное программмирование, ч.1, Петербургский государственный университет путей сообщения, 1996, 40 с.
3.Луценко М.М. Линейная алгебра. Учебное пособие. СПб: Петербургский государственный университет путей сообщения, 1999. – 121 с.
20