Решение задачи линейного программирования симплекс-методом
2. Рассмотрим ограничение (3) прямой задачи:
.
При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:
.
Т. о., при решении
задачи максимизации
ограничениям
прямой задачи,
имеющим знак
равенства,
соответствуют
двойственные
переменные,
не ограниченные
в знаке
.
3. Рассмотрим ограничение (4) прямой задачи:

В целевой
функции избыточные
переменные
имеют коэффициенты,
равные нулю
(
),
а искусственные
переменные
коэффициенты,
равные величине
штрафа со своим
знаком, в результате
для задачи
максимизации
получим:

Т. о., при решении
задачи максимизации
ограничениям
прямой задачи,
имеющим знак
,
соответствуют
неположительные
двойственные
переменные
.
4. Если в прямой задаче есть переменная, неограниченная в знаке, то в двойственной задаче получатся два ограничения, имеющие одинаковые коэффициенты при двойственных переменных, но разные знаки ограничений. Для удобства решения эти ограничения сворачивают в одно со знаком равенства (тем самым число ограничений двойственной задачи сводится к числу исходных переменных прямой задачи).
По аналогии можно записать условия двойственной задачи при решении задачи минимизации. Для удобства пользования некоторые соотношения при переходе от прямой задаче к двойственной приведены в таблице.
| Прямая задача | Двойственная задача | |||
| Целевая функция | Ограничения | Целевая функция | Ограничения | Переменные |
| Максимизация |
|
Минимизация |
|
|
| = |
|
|||
|
|
|
|||
| Минимизация |
|
Максимизация |
|
|
| = |
|
|||
|
|
|
|||
В двойственной
задаче переменные
могут быть
неотрицательными
(
),
не ограниченными
в знаке (
),
неположительными
(
).
При решении
ДЗ, как и ПЗ должны
выполняться
условия неотрицательности
ограничений
и переменных.
Для представления
двойственной
задачи в стандартной
форме используются
следующие
подстановки:
если переменная
не ограничена
в знаке, то
;
если
,
то
.
Такие подстановки следует использовать во всех ограничениях, содержащих эти переменные, а также в выражении для целевой функции.
После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что и для прямой задачи.
II. Практическая часть
1. Решение задачи линейного программирования графическим методом.
Дана следующая задача линейного программирования (ЗЛП).
![]()
![]()
![]()
![]()
,
![]()
1.1. Все ограничения
задачи
.
1.2. Переменная
ограниченна
в знаке, поэтому
.
Переменная
не ограничена
в знаке, поэтому
вводим замену
,
где
.
Область допустимых решений будет ограничиваться I и IV квадрантом.
1.3. Построение
ограничений
и градиента
целевой функции
:
1.4. Область допустимых решений – отрезок AB.
1.5. Точка А – оптимальная. Координаты т. А:

;
;
.
2. Решение задачи линейного программирования симплекс-методом.
Прямая задача.
Задачу
линейного
программирования
для любой вершины
в компактной
форме можно
представить
в виде:
![]()
![]()
![]()
Для получения используем алгоритм, приведённый в теоретической части.
1. Переход
от неравенств
к равенствам
по правилам
введения
дополнительных
переменных.
Исходную задачу
необходимо
привести к
стандартной
форме: введем
замену по переменной
,
и дополнительные
переменные:
![]()
![]()
![]()
![]()
,
![]()
Полученный
вид ЗЛП не позволяет
сформировать
начальный
допустимый
базис, т. к. нельзя
выделить единичные
орты во втором
и третьем равенствах.
Для получения
начального
допустимого
базиса введём
искусственные
переменные.
В результате
получим:
![]()
![]()
![]()
![]()
,
![]()
2. Общее число
переменных
определим по
формуле:
=3+2+2=7,
где
- число искусственных
переменных.
Число базисных
переменных
определяется
числом ограничений,
т. к.
,
то система
имеет три базисные
переменные
и
небазисные
переменные
.
3. Получение
- строки для СТ
(0). Приведём целевую
функцию к виду
.
Получим
из (2):
,
из (3):
![]()
![]()
4. Формирование симплекс – таблицы на первом шаге:
![]()
Начальный
базис
СТ
(0) РС
|
|
|
|
|
|
|
|
|
ПЧ | |
|
|
1 | -1-4M | 3+3M | -3M-3 | M | 0 | 0 | 0 | -12M |
|
|
0 | 1 | 2 | -2 | 0 | 1 | 0 | 0 | 4 |
|
|
0 | 3 | -4 | 4 | 0 | 0 | 1 | 0 | 12 |
|
|
0 | 1 | 1 | -1 | -1 | 0 | 0 | 1 | 0 |
5. Определение разрешающего столбца.
При решении
задачи максимизации
выбираем в
- строке максимально
отрицательный
коэффициент:
- включаемая
переменная.
6. Определение
разрешающей
строки:
– исключаемая
переменная.
7. Разрешающий элемент РЭ = 1.
8. Получение матрицы перехода
,
где В(0) - матрица
перехода
9. Определение элементов таблицы СТ(1) = В(0) СТ(0);
10. Исследование z-строки СТ(1) на условие оптимальности:
СТ(1)
| z |
|
|
|
|
|
|
|
ПЧ | |
| z | 1 | 0 | 4+7M | -7M-4 | -3M-1 | 0 | 0 | 1+4M | -12M |
|
|
0 | 0 | 1 | -1 | 1 | 1 | 0 | -1 | 4 |
|
|
0 | 0 | -7 | 7 | 3 | 0 | 1 | -3 | 12 |
|
|
0 | 1 | 1 | -1 | -1 | 0 | 0 | 1 | 0 |

СТ(2)
| z |
|
|
|
|
|
|
|
ПЧ | |
| z | 1 | 0 | 0 | 0 | 5/7 | 0 | M+4/7 | M-5/7 | 48/7 |
|
|
0 | 0 | 0 | 0 | 10/7 | 1 | 1/7 | -10/7 | 40/7 |
|
|
0 | 0 | -1 | 1 | 3/7 | 0 | 1/7 | -3/7 | 12/7 |
|
|
0 | 1 | 0 | 0 | -4/7 | 0 | 1/7 | 4/7 | 12/7 |
![]()
![]()
СТ(2) – оптимальная,
т. к. коэффициенты
при НБП
.
,
,
.
3. Решение задачи линейного программирования симплекс-методом.
Двойственная задача.
Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:
Прямая задачаДвойственная задача

![]()
![]()
![]()
(1)
(2)
![]()
![]()

Итак, получено:
,
,
.
2. Приведём
запись двойственной
задачи к канонической
форме. На основании
полученных
ОДР двойственных
переменных
введём необходимые
подстановки:
.
Для удобства решения свернём ограничения (1) и (2) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные.
![]()
(3)
(4)
3. Решим ДЗ симплекс методом:
Из (3): выразим![]()
Из (4) выразим:
![]()
![]()
СТ(0)
| W |
|
|
|
|
|
|
|
ПЧ | |
| W | 1 | -4-M | 7M-12 | 12-7M | 0 | -M | 0 | 0 | 4M |
|
|
0 | 1 | 3 | -3 | -1 | -1 | 1 | 0 | 1 |
|
|
0 | -2 | 4 | -4 | 1 | 0 | 0 | 1 | 3 |

СТ(1)
| W |
|
|
|
|
|
|
|
ПЧ | |
| W | 1 | -10/3M | 0 | 0 | 7/3M-4 | 4/3M-4 | -7/3M+4 | 0 | 5/3M+4 |
|
|
0 | 1/3 | 1 | -1 | -1/3 | -1/3 | 1/3 | 0 | 1/3 |
|
|
0 | -10/3 | 0 | 0 | 7/3 | 4/3 | -4/3 | 1 | 5/3 |

СТ(2)
-
W 





ПЧ W 1 -40/7 0 0 0 -12/7 -7/3M+4 -M+12/7 48/7 
0 -1/7 1 -1 0 -1/7 1/3 1/7 4/7 
0 -10/7 0 0 1 4/7 -4/3 -3/7 5/7
СТ(2) – оптимальная,
т. к. коэффициенты
при
![]()
,
,
![]()
Задание:
1. Изучить методы решения задачи линейного программирования (графический и симплекс-метод):
2. Для заданного варианта получить решение задачи линейного программирования:
- графическим методом;
- симплекс методом для прямой задачи;
- симплекс методом для двойственной задачи.