(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.
|