- •Методы оптимальных решений
- •Методические указания по выполнению контрольной работы
- •Оглавление
- •Симплекс-метод решения задач лп, обладающих очевидным начальным базисом
- •Симплекс-метод решения задач лп, обладающих очевидным начальным базисом и заданных в каноническом виде
- •Решение задач лп не обладающих очевидным начальным базисом двухэтапным симплекс-методом
- •Транспортная задача линейного программирования
- •Модели сетевого планирования и управления
- •Библиографический список
Симплекс-метод решения задач лп, обладающих очевидным начальным базисом
Задача 2. Решить задачу о лакокрасочной фабрике симплекс-методом.
Математическая модель задачи (смотрите пример1):
(1)
Приведём задачу к каноническому виду, приводя ограничения типа ˝˝ к ограничениям типа ˝=˝, вводя неотрицательные остаточные переменныеS1, S2, S3, S4, причём, , если знак в ограничении, и, если знак.
(2)
Выпишем расширенную матрицу ограничений (коэффициенты при неизвестных в ограничениях):
.
В матрице имеется единичная подматрица, число строк в которой равно количеству ограничений. Поэтому задача имеет очевидный начальный базис, т.к. столбцы единичной подматрицы соответствуют этим переменным.
Замечание 1. Единичная подматрица может получаться и путём перестановки столбцов.
Подставляем эти выражения в целевую функцию для получения Z-строки начальной симплекс-таблицы.
Замечание 2. В данной задаче базисные переменные можно было бы не выражать, т.к. Z не содержит базисных переменных.
Переносим в Z неизвестные в левую часть:
- Z-строка начальной симплекс-таблицы.
Строим начальную симплекс-таблицу (смотрите таблицу 1) и доводим её до оптимальной.
Таблица1
Б |
Z |
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
Реш. |
|
Ком. |
Z |
1 |
-3 |
-2 |
0 |
0 |
0 |
0 |
0 |
- |
Не опт. |
S1 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
6 |
6 |
x1→Б |
S2 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
8 |
4 |
Б→S2 |
S3 |
0 |
-1 |
1 |
0 |
0 |
1 |
0 |
1 |
- |
|
S4 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 |
- |
|
Данная симплекс-таблица не оптимальна, т.к. в Z-строке у переменных есть отрицательные коэффициенты (относительные оценки). Выбираем наименьшую отрицательную относительную оценку и эта переменная входит в базис: x1→Б (ведущий столбец). Делим элементы столбца ˝Решение˝ на положительные элементы ведущего столбца x1 и результаты записываем в столбец . Выбираем в столбценаименьшее число и эта переменная выходит из базиса: Б→S2 (ведущая строка). Обнуляем элементы ведущего столбца методом Гаусса (на пересечении ведущей строки и ведущего столбца получаем 1, а остальные 0). Следующую симплекс-таблицу (таблица 2) получаем следующим образом: ;;;;.
Таблица 2
Б |
Z |
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
Реш. |
|
Ком. |
Z |
1 |
0 |
-1/2 |
0 |
3/2 |
0 |
0 |
12 |
- |
Не опт. |
S1 |
0 |
0 |
3/2 |
1 |
-1/2 |
0 |
0 |
2 |
4/3 |
x2→Б |
x1 |
0 |
1 |
1/2 |
0 |
1/2 |
0 |
0 |
4 |
8 |
Б→S1 |
S3 |
0 |
0 |
3/2 |
0 |
1/2 |
1 |
0 |
5 |
- |
|
S4 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 |
- |
|
Таблица 2 не оптимальна. Для получения следующей таблицы 3 обнуляем элементы столбца x2.
Таблица 3
Б |
Z |
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
Реш. |
|
Ком. |
Z |
1 |
0 |
0 |
1/3 |
4/3 |
0 |
0 |
12 |
- |
опт. |
x2 |
0 |
0 |
1 |
2/3 |
-1/3 |
0 |
0 |
4/3 |
- |
|
x1 |
0 |
1 |
0 |
-1/3 |
2/3 |
0 |
0 |
10/3 |
- |
|
S3 |
0 |
0 |
0 |
-1 |
1 |
1 |
0 |
3 |
- |
|
S4 |
0 |
0 |
0 |
-2/3 |
1/3 |
0 |
1 |
2/3 |
- |
|
Получена оптимальная симплекс-таблица. Значения базисных переменных и находятся в столбце ˝Решение˝, а значения небазисных переменных равны нулю.
- максимальная прибыль.
- объёмы производства.
, т.к. .
.
Проверка (подставляем значения базисных переменных в канонический вид):