Материал: УП - Методы оптимальных решений

и доставляет min значение линейной функции

f(y) = b₁y₁ + b₂y₂+ … + b_my_m= b_iy_i.

Итак, в сокращенной форме записи имеем:

Такие задачи называются симметричными двойственными задачами.

Сравнивая симметричные двойственные модели можно установить следующее:

1) Если прямая задача на mах, то двойственная к ней задача на min и наоборот.

2) Коэффициенты С_j целевой функции прямой задачи являются сво­бодными членами ограничений двойственной задачи.

3) Свободные члены b_i ограничений прямой задачи и являются коэф­фициентами целевой функции.

4) Матрицы ограничений прямой задачи и двойственной задачи яв­ляются транспонированными друг к другу.

5) Число ограничений прямой задачи равно числу переменных двой­ственной задачи и наоборот.

6) Переменные прямой задачи и двойственной задачи неотрицательны.

Рассмотренные исходная и двойственная задачи могут быть экономически интерпретированы следующим образом.

Исходная задача. Сколько и какой продукции x_j (j = ) необходимо произвести, чтобы при заданных стоимостях С_j (j = ) единицы продукции и размерах имеющихся ресурсов b_i (i = ) максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача. Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b_i и величинах стоимости единицы продукции С_j минимизировать общую стоимость затрат?

Переменные y_i называются оценками или учетными, неявными ценами.

Как видно из рассмотренных задач, между их математическими моделями существует тесная связь. Матрица А системы ограничений исходной задачи является транспонированной матрицей в двойственной задаче. Коэффициенты С линейной функции исходной задачи являются свободными членами ограничений двойственной задачи, а свободные члены В ограничений исходной задачи являются коэффициентами линейной функции двойственной задачи.

Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

Пример 12. Составить модель двойственной задачи.

Таблица 22

Решение.

1. Пусть х₁, х₂, х₃, х₄ – объемы продукций П₁, П₂, Пз, П₄, планируемые к вы­пуску; Z – сумма ожидаемой выручки.

Математическая модель прямой задачи:

Найти max z = 65х₁ + 70х₂ + 60х₃ + 120х₄, если

2. Тогда математическая модель двойственной задачи имеет вид: пусть y₁, y₂, y₃ – стоимость ресурсов P₁, P₂, P₃,тогда найти min f = 4800y₁ + 2400y₂ + 1500y₃, если

Пример 14. Прямая задача относится к симметричным двойственным задачам на отыскание min значения линейной функции. Для того, чтобы можно было записать двойственную задачу, ее модель ограничений должна иметь вид Ax ≥ B.

min z = 2х₁ + х₂ + 5х₃,

Двойственная задача:

max f = – 4у₁ + 5у₂ + 6у₃,

Двойственные задачи могут иметь и несимметричный вид. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенства, а двойственной – в виде неравенства, причем в последней переменные могут быть и отрицательными.

4.2. Двойственный симплексный метод

Воспользуемся (без дока­зательства) теоремой для решения двойственных задач. Теорема устанавливает связь между оптимальными планами пары двойственных задач.

Теорема (теорема двойственности): если одна из двойственных задач имеет оптимальное ре­шение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны Z(x*) = f(у*). При этом свободным переменным одной задачи сопоставляются базисные переменные другой и наоборот.

Пример 15. По условиям примера 1 найти:

1) ассортимент выпускаемой продукции, обеспечивающей предпри­ятию max выручки;

2) оценки ресурсов, используемых при производстве продукции.

Решение:

1) Симплексным методом решаем задачу, модель которой уже составлена.

Таблица 23

После второй итерации получим все оценки значит найденный опорный план:

оптимален и – max.

Основные переменные показывают, что продукцию П₁ и П₂ выпускать не целесообразно ( = 0, = 0), а продукции П₃ произвести 400 ед., продукции П₄ – 500 ед.

Дополнительные переменные показывают, что ресурсы Р₁ и Р₂ используются полностью ( = = 0), а вот ресурса Р₃ осталось 200 ед. неиспользованными.

2) Определимся с переменными оптимального плана двойственной задачи: двойственной оценки В прямой задаче х₁, х₂ , х₃, х₄ являются свободными переменными, а х₅, х₆, х₇ – базисными.

В двойственной задаче свободными переменными будут у₁, у₂, у₃, а у₄, y₅, у₆, y₇ – базисными переменными.

Соответствие между переменными будет:

x ₁ х₂ х₃ х₄ х₅ х₆ х₇

СП БП