Материал: 3094
соответствующие им коэффициенты в целевой функции с противоположными знаками.
В последней строке записывают значение целевой функции F0 ( X0 ) при данном опорном плане X 0{ f1, f2 , f3 , f4 ,0,0}, которое вычисляется по формуле
4
F0 ci fi ,
i 1
и далее оценки свободных неизвестных, найденные по формуле
|
4 |
|
|
j |
ci hij |
c j ; |
j 1, 2, 3, 4, 5, 6. |
|
i 1 |
|
|
Если среди оценок |
j есть отрицательные, то опорный план X 0 не |
||
является оптимальным и значение функции F0 можно улучшить. Для этого нужно пересчитать симплексную таблицу, выбрав соответствующим образом ключевой элемент, стоящий на пересечении ключевой строки и ключевого столбца. За ключевой столбец берут тот, в котором находится отрицательная оценка. (Если отрицательных оценок больше одной, то рекомендуется выбирать столбец с наибольшей по абсолютной величине оценкой.)
Для нахождения ключевой строки составляем отношения правых частей fi к положительным элементам ключевого столбца. Полученные значения записываются в последний столбец. Из них выбираем наименьшее, которое и указывает нам ключевую строку.
Пример 1.1. Решить задачу линейного программирования с известным опорным планом X 0{x1, x2 , x3 , x4 ,0,0} симплексным методом.
F(X ) x2 |
x3 4x5 |
5x6 max, |
|
||||
x1 |
|
2x5 3x6 1, |
|
||||
|
x2 |
|
|
x5 3x6 |
13, |
|
|
|
|
|
|||||
|
|
x3 |
4x5 |
x6 |
26, |
(1.1) |
|
|
|
||||||
|
|
x4 |
|
|
x5 3x6 0, |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
x 0. |
|
|
|
||
|
|
i |
|
|
|
|
|
Решение.
Составим симплексную таблицу для системы (1.1).
|
|
|
0 |
1 |
1 |
0 |
4 |
5 |
|
|
fi |
0 |
C |
Б |
fi |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||||
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
his |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
x1 |
1 |
1 |
0 |
0 |
0 |
–2 |
3 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
x2 |
13 |
0 |
1 |
0 |
0 |
–1 |
3 |
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
x3 |
26 |
0 |
0 |
1 |
0 |
4 |
1 |
32 |
|
|
|
0 |
x4 |
0 |
0 |
0 |
0 |
1 |
1 |
–3 |
–1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F0 13 |
0 |
0 |
0 |
0 |
–1 |
–3 |
–17 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
Поскольку в последней строке есть отрицательные оценки свободных неизвестных 5 1, 6 3, то опорный план X0{1,13, 26, 0, 0, 0} не является оптимальным.
Для пересчета таблицы за ключевой столбец выберем столбец x6 с оценкой 6 3. Для определения ключевой строки составим отношения элементов столбца fi к положительным элементам соответствующих строк
столбца x6 . Из полученных соотношений 13; 133 ; 26 выбираем наименьшее:
min{13 ; 133 ; 26} 13 . Поэтому ключевой строкой будет первая, а ключевым
элементом – элемент 3, отмеченный в таблице кружком (см. следующую таблицу).
Пересчет таблицы с помощью ключевого элемента 3 будем производить по следующему правилу. Элементы ключевой строки разделим на ключевой элемент. Элементы ключевого столбца, кроме ключевого элемента, заменим нулями. Все остальные элементы пересчитаем по правилу прямоугольника: при пересчете каждого элемента в таблице выделяется прямоугольник, диагональ которого соединяет пересчитываемый элемент с ключевым. Из произведения этих элементов вычитаем произведение элементов, стоящих на концах другой
диагонали этого прямоугольника. Полученная разность делится на ключевой элемент.
|
|
|
|
0 |
–1 |
1 |
0 |
4 |
–5 |
|
|
fi |
0 |
C |
|
Б |
fi |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|||||||
|
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
his |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
x1 |
1 |
1 |
0 |
0 |
0 |
–2 |
3 |
3 |
|
1/3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
x2 |
13 |
0 |
1 |
0 |
0 |
–1 |
3 |
16 |
|
13/3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
–1 |
|
x3 |
26 |
0 |
0 |
1 |
0 |
4 |
1 |
32 |
|
26 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
x4 |
0 |
0 |
0 |
0 |
1 |
1 |
–3 |
–1 |
|
|
– |
fi F0 13 |
0 |
0 |
0 |
0 |
–1 |
–3 |
–17 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
x6 |
1/3 |
1/3 |
0 |
0 |
0 |
–2/3 |
1 |
1 |
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
x2 |
12 |
–1 |
1 |
0 |
0 |
1 |
0 |
13 |
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
–1 |
|
x3 |
77/3 |
–1/3 |
0 |
1 |
0 |
14/3 |
0 |
31 |
|
77/14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
x4 |
1 |
1 |
0 |
0 |
1 |
–1 |
0 |
2 |
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F1 12 |
1 |
0 |
0 |
0 |
–3 |
0 |
–14 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
x6 |
4 |
2/7 |
0 |
1/7 |
0 |
0 |
1 |
38/7 |
|
|
|
1 |
|
x2 |
13/2 |
–13/14 |
1 |
–3/14 |
0 |
0 |
0 |
89/14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
–4 |
|
x5 |
11/2 |
–1/14 |
0 |
3/14 |
0 |
1 |
0 |
93/14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
x4 |
13/2 |
13/14 |
0 |
13/14 |
1 |
0 |
0 |
121/14 |
|
|
|
F2 9 / 2 |
11/14 |
0 |
9/14 |
0 |
0 |
0 |
84/14 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
После первого перерасчета мы получили вторую таблицу, из которой следует, что опорный план X1{0, 12, 773 , 1, 0, 13} не является оптимальным, так
как в последней строке имеется отрицательная оценка выбрав по указанному выше правилу ключевой элемент вторую таблицу и получаем третью таблицу, в которой
оценок. Это |
говорит о |
том, что мы получили |
||||||||||
X |
|
{0, |
13 |
, 0, |
13 |
, |
11 |
, 4}. |
При этом F |
|
9 |
. |
|
опт |
2 |
|
2 |
2 |
|
max |
2 |
|
|||
|
|
|
|
|
|
|||||||
5 3. Поэтому,
143 , пересчитываем
нет отрицательных оптимальный план
Ответ: оптимальный план {0, 132 , 0, 132 , 112 , 4}; Fmax 92 .
Пример 1.2. Решить каноническую задачу линейного программирования
F X 3x1 2x2 x5 |
max , |
|
|
|
||||
x1 2x2 x3 |
|
3x5 |
|
|
7, |
|
||
|
|
8x2 |
x4 4x5 |
|
10, |
|
||
3x1 |
|
(1.2) |
||||||
4x |
|
|
2x |
|
x |
12, |
|
|
|
1 |
|
|
5 |
6 |
|
|
|
|
|
5 |
x j |
0, |
j 1, 2, ..., 6. |
|
||
Решение. Очевидно, что данная каноническая задача имеет невырожденный опорный план X 0 0; 0; 7;10; 0;12 и система (1.2) имеет вид, в котором каждая из соответствующих этому плану базисных неизвестных находится лишь в одном из уравнений (1.2) и имеет единичный коэффициент.
Составим симплексную таблицу (табл.1.2).
В последней строке таблицы есть отрицательная оценка
(свободной неизвестной x1 ), поэтому опорный план X 0 не является оптимальным. Столбец с отрицательной оценкой 1 3 выберем ключевым. Для определения ключевой строки составим отношения элементов столбца f к соответствующим положительным элементам ключевого столбца. Эти отношения запишем в соответствующие клетки последнего столбца таблицы
Таблица 1.2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
–3 |
2 |
0 |
0 |
1 |
0 |
|
|
fi |
|
|
С |
Б |
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
his |
|
|||||
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
x3 |
7 |
–1 |
2 |
1 |
0 |
3 |
0 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
x4 |
10 |
3 |
8 |
0 |
1 |
–4 |
0 |
18 |
10 |
|
||
|
|
|
|
|||||||||||
3 |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
x6 |
12 |
|
4 |
0 |
0 |
0 |
–2 |
1 |
15 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F X 0 0 |
–3 |
2 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
; 3 3 . |
|
1.2. Из полученных отношений выбираем наименьшее: min |
|
|
|
||
3 |
|
|
Поэтому третья строка является ключевой, а элемент 4, расположенный в ключевой строке и ключевом столбце, является ключевым элементом. Применяя далее симплексный метод, получаем таблицу и соответствующий
(невырожденный) |
опорный |
план |
X 1 3; 0;10;1; 0; 0 . |
Видим, что |
|
F X 1 F X 0 . |
Так как в последней |
строке |
таблицы есть |
отрицательная |
|
оценка (свободной неизвестной |
x ), то план |
X 1 не является оптимальным. |
|||
|
|
5 |
|
|
|
Выбрав ключевым столбцом столбец с отрицательной оценкой, ключевой строкой – первую строку, получаем ключевой элемент 52 . Преобразовав последнюю таблицу соответствующим образом, получаем таблицу 1.4.
Поэтому третья строка является ключевой, а элемент 4, расположенный в ключевой строке и ключевом столбце, является ключевым элементом. Применяя далее симплексный метод, получаем таблицу и соответствующий (невырожденный) опорный план X 1 3; 0;10;1; 0; 0 .