ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 811
Скачиваний: 2
Таб.2. Преобразование симплекс-таблицы
|
Базисные переменные |
Свободные члены |
Свободные переменные |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
|
|
|
|
|
… |
|
|
|
x j |
|
|
… |
|
|
xk |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
b - |
bi × a1 j |
|
|
|
a - |
a1 j × ai1 |
|
|
|
|
|
|
|
|
a |
|
|
|
|
a |
- |
a1j × aik |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
1 |
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 j |
|
|
|
|
|
|
|
|
|
|
|
|||
|
xk+1 |
|
|
aij |
|
|
|
|
|
|
aij |
|
… |
- |
|
|
|
|
|
|
… |
|
1k |
|
|
|
aij |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
aij |
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
… |
… |
|
|
|
|
|
|
… |
|
|
|
|
… |
|
|
… |
|
|
… |
|
|
… |
|
|
|
|
|
||||||||||||
|
x |
k +i |
bi / aij |
|
|
|
|
|
|
ai1 |
|
|
|
|
|
|
… |
|
|
1 |
|
|
|
… |
|
|
aik |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
aij |
|
|
|
|
|
|
|
|
aij |
|
|
|
|
aij |
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
… |
… |
|
|
|
|
|
|
… |
|
|
|
|
… |
|
|
… |
|
|
… |
|
|
… |
|
|
|
|
|
||||||||||||
|
x k + m |
bm - |
bi × amj |
|
|
am1 - |
|
amj × ai1 |
|
… |
- |
amj |
|
|
… |
|
amk - |
amj ×aik |
||||||||||||||||||||||
|
aij |
|
|
|
|
aij |
|
|
|
|
|
|
|
aij |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
aij |
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Целевая функция Z |
|
|
c/ |
×b |
|
|
|
|
|
|
c |
/ |
× a |
|
|
|
|
/ |
|
|
|
|
|
|
|
c/j ×aik |
|||||||||||||
|
c/ - |
j |
i |
|
|
c/ |
- |
|
|
j |
i1 |
|
|
- |
|
|
c j |
|
|
|
|
c/ |
- |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
0 |
|
aij |
|
|
1 |
|
|
|
|
|
aij |
|
… |
|
|
|
|
|
|
… |
|
k |
|
|
|
aij |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
aij |
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
П р и м е р . |
|
Найти |
|
наибольшее |
|
значение |
|
целевой |
||||||||||||||||||||||||||||||
функции z при заданных ограничениях: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
Z = 6× x1 + x2 ® max |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
ì3× x1 - x2 ³ 9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
ï |
|
|
|
|
|
|
|
£ 50 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
í2× x1 + 3× x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
ï- x |
+ 4× x |
2 |
³ 18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
î |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x1³ 0, x2 ³ 0
Исходную стандартную задачу линейного программирования (СЗЛП) приведем к каноническому виду (КЗЛП). Для этого введем дополнительные переменные, учитывая знаки неравенств-ограничений. Если ограничение- неравенство имеет знак «≥», то дополнительную переменную вводим со знаком «-», в противном случае – со знаком «+».
27
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
|
СЗЛП |
|
|
КЗЛП |
|
|||||
Z = 6 × x1 + x2 ® max |
Z = 6 × x1 + x2 ® max |
|||||||||
ì3× x1 - x2 ³ 9 |
ì3× x1 - x2 - x3 = 9 |
|||||||||
ï |
× x1 + 3× x2 £ 50 |
ï |
× x1 + 3 |
× x2 +x4= 50 |
||||||
í2 |
í2 |
|||||||||
ï- x + 4 × x |
2 |
³ 18 |
ï- x + 4 × x |
2 |
- x |
5 |
= 18 |
|||
î |
1 |
|
î |
1 |
|
|
|
|||
x1³ 0, x2 ³ 0 |
|
x1³ 0, x2 ³ 0 |
|
|
|
|||||
В |
качестве базисных |
переменных |
удобно выбрать |
|||||||
x3, x4, x5 , так как относительно этих переменных легко решить систему линейных уравнений: {x3, x4, x5} - базисные переменные; {x1, x2} - свободные переменные.
Z = 6× x1 + x2
x3 = -9 + 3× x1 - x2 x4= 50 - 2× x1 - 3× x2 x5 = -18 - x1 + 4× x2
Составим первую симплекс-таблицу: свободные члены записываем без изменения знаков, а коэффициенты при свободных переменных – с противоположными знаками.
|
Базисные |
|
Свободные |
Свободные |
|
|
|||||
|
|
переменные |
|
|
|||||||
|
переменные |
|
|
члены |
|
|
|
|
|
|
|
|
|
x1 |
|
x2 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
|
|
|
-9 |
-3 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x4 |
|
|
|
50 |
2 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x5 |
|
|
|
-18 |
1 |
|
-4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z |
|
|
|
0 |
-6 |
|
-1 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
Базисное |
решение |
X = {0, 0, - 9, 50, -18} |
- |
|||||||
недопустимое, |
т.к. |
|
имеются |
отрицательные |
элементы |
||||||
( x3 < 0, x5 < 0 ). |
Данная |
симплекс-таблица соответствует |
точке |
||||||||
начала координат на |
рис.6. Ограничения совместны, |
т.к. в |
|||||||||
|
|
|
|
|
|
|
|
|
|
28 |
|
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
строках с отрицательными свободными членами имеются ещё отрицательные элементы. Необходимо найти разрешающий элемент и провести преобразование симплекс-таблицы.
Найдём разрешающий элемент. Выберем наименьший
отрицательный элемент в строках с отрицательными свободными членами. Это -4. Столбец, в котором находится этот элемент ( x2 ), принимаем в качестве разрешающего столбца
(помечен стрелкой).
Для нахождения разрешающей строки определяем минимальное положительное отношение свободных членов к
элементам |
|
разрешающего |
столбца. |
Так |
как |
|||||
50 |
|
−18 |
−18 |
|
|
|
|
|
||
min{ |
|
, |
|
} = |
|
= 4,5 , то в |
качестве разрешающей |
строки |
||
3 |
− 4 |
− 4 |
||||||||
получаем x5 . |
|
|
|
|
|
|
||||
|
|
Элемент, |
находящийся |
на |
пересечении |
разрешающих |
||||
столбца и строки, является разрешающим элементом (выделен рамкой). Он указывает, что базисную переменную x5
переводим в свободные, а свободную переменную x2 - в
базисные.
Преобразуем симплекс-таблицу, используя правила преобразования:
1.Ячейку разрешающего элемента, равного «-4», заполняем значением, обратным значению разрешающего элемента (-1/4=-0,25).
2.Ячейки разрешающей строки x5 заполняем
элементами, стоящими в этих ячейках, деленными на разрешающий элемент «-4». Например, элемент, находящийся на пересечении столбца свободных членов и строки x5 , будет
равен |
−18 |
= 4 |
1 |
. |
|
|
|
− 4 |
2 |
|
|
|
|||
|
|
|
|
|
|
||
|
3. |
Ячейки |
разрешающего |
столбца |
заполняем |
||
элементами, стоящими в этих ячейках, деленными на разрешающий элемент с обратным знаком «4». В частности, элемент, находящийся на пересечении столбца x2 и строки x4 ,
будет равен 34 .
29
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
4.Остальные ячейки заполняем значениями, стоящими
вэтих ячейках, минус произведение элементов, стоящих в
соответствующем разрешающем столбце и в соответствующей разрешающей строке, деленное на разрешающий элемент «-4». Например, элемент, находящийся на пересечении столбца
свободных |
членов |
и |
|
|
|
|
|
|
строки |
|
|
x3 , |
|
|
будет |
|
равен |
||||||||||||||||||||
- 9 - |
|
1×(-18) |
= -13 |
1 |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
- 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
В результате преобразования симплекс-таблицы |
||||||||||||||||||||||||||||||||||
получим: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Базисные |
Свободные |
|
|
|
|
Свободные |
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
переменные |
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
переменные |
|
члены |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
x1 |
|
|
|
x5 |
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
|
|
|
|
-13 |
1 |
|
|
|
- 2 |
|
|
3 |
|
|
|
|
1 |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
x4 |
|
|
|
|
36 |
1 |
|
|
|
|
2 |
3 |
|
|
|
|
|
3 |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|||||||||||
|
|
|
x2 |
|
|
|
|
4 |
1 |
|
|
|
|
|
- |
1 |
|
|
|
|
|
- |
|
1 |
|
|
|
||||||||||
|
|
|
|
|
|
|
2 |
|
|
|
|
|
4 |
|
|
|
|
4 |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
Z |
|
|
|
|
4 |
1 |
|
|
|
|
|
- 6 |
|
1 |
|
|
|
- |
|
1 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
Базисное |
решение |
X = {0; 4 |
|
1 |
; -13 |
1 |
; 36 |
1 |
; 0} |
- |
||||||||||||||||||||||||
|
|
|
2 |
|
2 |
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
||||||||||
недопустимое, |
т.к. |
есть |
|
|
|
|
отрицательный |
элемент |
|
|
|
( x3 < 0 ). |
|||||||||||||||||||||||||
Ограничения совместны, т.к. в строке с отрицательным свободным членом имеется ещё отрицательный элемент.
В качестве разрешающего столбца выбираем столбец x1.
-13 |
|
1 |
|
36 |
|
1 |
|
|
-13 |
|
1 |
|
||||
2 |
|
2 |
|
|
2 |
|
||||||||||
Вычисляя min{ |
|
, |
|
|
} = |
|
@ 4,9 , получаем, что в |
|||||||||
|
|
|
|
|
|
|
||||||||||
- 2 |
3 |
|
|
2 |
3 |
|
|
|
- 2 |
3 |
|
|
||||
4 |
|
|
4 |
|
|
|
4 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
||||||
качестве разрешающей строки следует выбрать x3 . Базисную
30
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com