Практикум по решению линейных задач математического программирования
Эти требования можно записать в виде следующей ЗЛП:
![]()

,
![]()
Или в краткой форме записи:
(4)
,
(5)
,
(6)
Полученную
задачу (4) – (6) называют
двойственной.
Переменные
называются
двойственными
оценками, или
теневыми ценами.
Задачи (1) – (3) и (4) – (6) называют парой взаимно двойственных симметричных задач, т. к. они обладают следующими свойствами:
Если в одной задаче ищется максимум целевой функции, то в другой – минимум.
Коэффициенты при переменных в целевой функции одной задачи являются правыми частями ограничений другой задачи и, наоборот.
В каждой
задаче система
ограничений
задается в
виде неравенств,
причем все они
одного смысла:
если задача
на max, то все
неравенства
содержат знаки
«
»,
если на min, то
все неравенства
содержат знаки
«
».
Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи.
Условие неотрицательности переменных сохраняется в обеих задачах.
Примечание: Понятие «прямой» и «двойственной» задач условно.
2) Построение модели двойственной задачи
Используя свойства (1–6), покажем на конкретном примере построение двойственной задачи.
Пример. Пусть исходная задача имеет вид:
![]()

,
![]()
Нужно составить к ней двойственную.
Решение. Запишем расширенную матрицу системы ограничений и транспонируем ее.
| 1 | –1 | 2 | 2 | 1 | 2 | 5 | 11 | 2 | |||
| 2 | 1 | –3 | 4 | АТ= | –1 | 1 | –1 | 1 | 3 | ||
| А = | 5 | –1 | 1 | 3 | 2 | –3 | 1 | 2 | 1 | ||
| 11 | 1 | 2 | 1 | 2 | 4 | 3 | 1 | min | |||
| 2 | 3 | 1 | max |
Теперь
запишем двойственную
задачу по АТ
с переменными
,
.
![]()

,
.
Пример. К заданной задаче записать двойственную:

Решение.
Так как задача
на min, то все
неравенства
должны иметь
знаки «
».
С этой целью
второе ограничение
умножим на
(–1); при этом знак
неравенства
изменится на
противоположный.
Теперь задача
будет иметь
вид:
![]()
![]()
,
![]()
Запишем матрицы А и АТ.
| 1 | 1 | 1 | 1 | –2 | 5 | |||
| А = | –2 | –3 | –5 | АТ= | 1 | –3 | 2 | |
| 5 | 2 | min | 1 | –5 | max |
Двойственная задача:
![]()
![]()
,
.
3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задач
Рассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции – П1, П2, П3. Для этого оно располагает объемами ресурсов 3-х видов Р1, Р2, Р3. Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:
|
Пj Рi |
П1 | П2 | П3 |
Объем
|
| Р1 | 4 | 2 | 1 | 180 |
| Р2 | 3 | 1 | 1 | 210 |
| Р3 | 1 | 2 | 5 | 244 |
|
Цена
|
10 | 14 | 12 |
Требуется:
построить модель исходной и двойственной задач;
решить исходную задачу симплексным методом;
найти оптимальное решение двойственной задачи, используя проверочную строку последней симплексной таблицы;
дать экономический анализ основным и дополнительным переменным оптимальных решений обеих задач;
в ответе записать оптимальные решения обеих задач и значения их целевых функций; указать наиболее дефицитный ресурс и наиболее убыточный вид продукции.
Решение. 1. Построим модель исходной задачи
![]()

,
.
Здесь х1, х 2, х3 – план выпуска продукции.
Составим математическую модель двойственной задачи:
![]()

,
.
2. Решим исходную задачу симплексным методом.
Запишем ее канонический вид:
![]()

,
.
х4,
х5, х6 –
дополнительные
и они же базисные
переменные.
Начальный
опорный план
(0;
0; 0; 180; 210; 244).
| Базис |
|
В | 10 | 14 | 12 | 0 | 0 | 0 |
|
|
|
|
|
|
|
|
||||
|
|
0 | 180 | 4 | 2 | 1 | 1 | 0 | 0 | 90 |
|
|
0 | 210 | 3 | 1 | 1 | 0 | 1 | 0 | 210 |
|
|
0 | 244 | 1 | 2 | 5 | 0 | 0 | 1 | 122 |
|
|
0 | –10 | –14 | –12 | 0 | 0 | 0 | таб. 1 | |
| Базис |
|
В | 10 | 14 | 12 | 0 | 0 | 0 |
|
|
|
|
|
|
|
|
||||
|
|
14 | 90 | 2 | 1 | 0,5 | 0,5 | 0 | 0 | 180 |
|
|
0 | 120 | 1 | 0 | 0,5 | –0,5 | 1 | 0 | 240 |
|
|
0 | 64 | –3 | 0 | 4 | –1 | 0 | 1 | 16 |
|
|
1260 | 18 | 0 | –5 | 7 | 0 | 0 | таб. 2 | |
|
|
14 | 82 | 2,375 | 1 | 0 | 0,625 | 0 | –0,125 | |
|
|
0 | 80 | 1,375 | 0 | 0 | 0,125 | 1 | –0,625 | |
|
|
12 | 16 | –0,75 | 0 | 1 | –0,25 | 0 | 0,25 | |
|
|
1340 | 14,25 | 0 | 0 | 5,75 | 0 | 1,25 | таб. 3 | |
|
|
|
|
|
|
|
||||
Так как
все оценки
,
то получен
оптимальный
план:
=
(0; 82; 16; 0; 80; 0);
=
1340.
3. Найдем оптимальное решение двойственной задачи, используя последнюю проверочную строку симплексной таблицы и соотношение между переменными прямой и двойственной задач.
|
|
дополнительные переменные | ||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| дополнительные переменные | основные переменные | ||||
Откуда:
5,75;
0;
1,25;
14,25;
0;
0.
=
(5,75; 0; 1,25; 14,25; 0; 0);
1340.
Таким
образом получили
=
1340.
4. Проанализируем основные и дополнительные переменные оптимальных решений обеих задач. Основные переменные исходной задачи – это планируемый выпуск продукции.

Продукцию І-го вида к выпуску не планируют, ІІ-го вида – в количестве 82 ед. и ІІІ-го вида – в количестве 16 ед.
Дополнительные переменные исходной задачи показывают остатки сырья.

Сырье І и ІІІ видов израсходовано полностью. А сырье ІІ вида осталось в количестве 80 ед.
Основные
переменные
двойственной
задачи характеризуют
дефицитность
сырья: если
,
то сырье дефицитное;
если
,
то сырье недефицитное.

Таким образом, сырье І и ІІІ видов дефицитное, причем наиболее дефицитное сырье І-го вида. Сырье ІІ вида недефицитное.
Дополнительные
переменные
двойственной
задачи характеризуют
рентабельность
продукции. При
этом, если
,
то продукция
нерентабельна.

По этому соотношению видно, что продукция І вида нерентабельна, а ІІ и ІІІ – рентабельна.
Ответ:
=
(0; 82; 16; 0; 80; 0);
=
1340;
=
(5,75; 0; 1,25; 14,25; 0; 0);