|
(C) Alternative_Simplex
|
|
(C) Alternative_Simplex
Симплекс-метод
решения задачи линейного программирования Начальные данные: Система
ограничений: 1*X1+2*X2+3*X3
<= 100, 3*X1-9*X2+7*X3
<= 200, 3*X1+8*X2+1*X3
<= 300, Целевая функция: L=2*X1+3*X2+4*X3
->max. Приведем систему
ограничений к каноническому виду. Введем новые
неотрицательные сменные (балансовые) переменные и превратим неравенства в
равенства по такому правилу. Если имеет место знак <=, то прибавляем к
левой части новую переменную, если имеет место знак >=, то переменную
вычитаем. Получим каноническую систему ограничений: 1*X1+2*X2+3*X3+X4=100, 3*X1-9*X2+7*X3+X5=200, 3*X1+8*X2+1*X3+X6=300, Ранг матрицы
системы ограничений: 1.000
2.000 3.000 1.000
0.000 0.000 А= 3.000 -9.000
7.000 0.000 1.000
0.000 3.000
8.000 1.000 0.000
0.000
1.000 и ранг расширенной
матрицы системы ограничений: 1.000
2.000 3.000 1.000
0.000 0.000 100.000
A’=3.000
-9.000 7.000 0.000
1.000 0.000 200.000
3.000
8.000 1.000 0.000
0.000
1.000 300.000 совпадают и
равняются 3, что свидетельствует о совместности системы
ограничений и то, что 3 базисные переменные можно выразить через 3 свободные
переменные. X3=
9.0909-0.3636X4-0.0909X1+ 0.0909X6, X5=463.6364+
2.9545X4-5.6364X1-1.8636X6, X2=36.3636+
0.0455X4-0.3636X1-0.1364X6, Целевая функция: L=145.4545-1.3182X4+
0.5455X1-0.0455X6. Симплекс-таблица |-----------|---------|---------|---------|---------|---------|---------|---------| | Базисные |Свободные| |
| | | | | | Переменные|
Члены | X1
| X2 |
X3 | X4
| X5 |
X6 | |-----------|---------|---------|---------|---------|---------|---------|---------| | X3
| 9.0909 | 0.0909 |
0.0000 | 1.0000 | 0.3636 |
0.0000 | -0.0909 | | X5
|463.6364 | 5.6364 | -0.0000
| 0.0000 | -2.9545 | 1.0000 |
1.8636 | | X2
| 36.3636 | 0.3636 | 1.0000 |
0.0000 | -0.0455 | 0.0000 | 0.1364 | |-----------|---------|---------|---------|---------|---------|---------|---------| | L
|145.4545 | -0.5455 | -0.0000 |
0.0000 | 1.3182 | 0.0000 |
0.0455 | |-----------|---------|---------|---------|---------|---------|---------|---------| Выясним, есть ли в
последней строке отрицательные оценки. Таких чисел 2:
-0.5455 -0.0000. Берем число -0.5455 и просматриваем строку для X1. В этом столбике 3 положительных элемента:
0.0909 5.6364 0.3636.
Делим на эти числа
соответствующие свободные члены. Получим: 100.0000 82.2581
100.0000. Из полученных
частных наименьшим есть 82.2581. Соответственно,
разрешающим есть элемент 5.6364,
который стоит на пересечении строки для X5 и
столбика для X1. Новый базис
состоит из векторов: X3 X1
X2 Для получения
следующей таблицы умножим строку с разрешающим элементом на 0.1774, для того, чтобы получить на месте
разрешающего элемента 1 и полученную таким образом строку пишем на
месте предшествующей. К каждой другой
строке прибавляем полученную, которую умножаем на такое число, чтобы в клетках для X1 появились нули, и пишем преобразованные строки на
месте предыдущих. Завершена 1
итерация. Симплекс-таблица |----------|---------|---------|---------|---------|---------|---------|---------| | Базисные
|Свободные| | | | | | | |Переменные| Члены
| X1 |
X2 | X3
| X4 |
X5 | X6
| |----------|---------|---------|---------|---------|---------|---------|---------| | X3
| 1.6129 | 0.0000 |
0.0000 | 1.0000 | 0.4113 | -0.0161 | -0.1210 | | X1
| 82.2581 | 1.0000 | 0.0000 |
0.0000 | -0.5242 | 0.1774 | 0.3306 | | X2
| 6.4516 | 0.0000 |
1.0000 | 0.0000 | 0.1452 | -0.0645 | 0.0161 | |----------|---------|---------|---------|---------|---------|---------|---------| | L
|190.3226 | 0.0000 | 0.0000 |
0.0000 | 1.0323 | 0.0968 |
0.2258 | |----------|---------|---------|---------|---------|---------|---------|---------| В последней
индексной строке нет отрицательных элементов. Оптимальный план
получен! X3= 1.6129. X1= 82.2581. X2= 6.4516. Другие переменные
имеют нулевое значение. Значение целевой
функции=190.3226. |
| РЕКЛАМА: |