Особые случаи решения ЗЛП

1. Если все компоненты вектора, подлежащего вводу в базис не положительны, то ЗЛП решений не имеет вследствие неограниченности сверху целевой функции:

2.  Если нулевая оценка симплекс-разности соответствует вектору, не входящему в базис, то в общем случае это означает, что оптимальный план не единственный.

 

 

Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана

Каждой задаче линейного программирования соответствует другая задача, называемая двойственной по отношению к исходной.

Актуальность темы: Для чего составляют и решают двойственные задачи? – для того, чтобы провести анализ решения исходной задачи, а именно, ответить на следующие вопросы:

1. Какой ресурс более дефицитен в отношении принятого в задаче показателя эффективности и, следовательно, больше сдерживает рост прибыли?

2. Как изменится прибыль при изменении запаса ресурсов?

3. Каковы нормы заменяемости ресурсов  (не абсолютные, а относительные, т.е. рассматриваемые с точки зрения конечного эффекта)?

4. Выгодно или нет вводить в план производства новые изделия?

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

Заметим, что 2-ая задача контрольной работы – задача, решаемая с использованием теории двойственности.

Ранее была рассмотрена задача ЛП об использовании ограниченных ресурсов (Тема 1.).

Запишем модель задачи ЛП в общем виде для для m- видов сырья и n- видов продукции.

Назовем ее задача I (исходная). Рядом запишем модель двойственной задачи.

 

 

Задача I (исходная)

Задача II (двойственная)

F = c1x1 + c2x2 +…+ cnxn → max при ограничениях: a11x1 + a12x2 + …+ a1nxn ≤ b1, a21x1 + a22x2 + …+ a2nxn ≤ b2, ……………………………… am1x1 + am2x2 + …+ amnxn ≤ bm, x1, …,n ≥ 0 Составить такой план выпуска продукции X=(x1,x2,…,xn), при котором прибыль от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Z = b1y1 + b2y2 +…+ bmym → min при ограничениях: a11y1 + a21y2 + …+ am1ym ≥ c1, a12y1 + a22y2 + …+ am2ym ≥ c2, ……………………………… a1ny1 + a2ny2 + …+ amnym ≥ cn, y1, …,m ≥ 0  Найти такой набор цен (оценок) ресурсов Y=(y1,y2,…,ym), при котором общие затраты на ресурсы будут минимальными при условии, что выручка от продажи ресурсов будет не меньше той суммы, которую предприятие может получить при переработке сырья в готовую продукцию. .

 

Экономическая интерпретация прямой задачи следующая: составить такой план выпуска продукции X=(x₁,x_2,…,x_n), при котором прибыль от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Рассмотрим экономическую интерпретацию двойственной задачи.

Предположим, что некоторая организация решила закупить ресурсы S₁,S₂,…,S_m предприятия и необходимо установить оптимальные цены на эти ресурсы: обозначим их y₁,y₂,…,y_m.

1) Покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z были минимальны: Z = b₁y₁ + b₂y₂ +…+ b_my_m → min

2) С другой стороны, предприятие, продающее ресурсы, заинтересовано в том чтобы полученная прибыль (выручка) от продажи ресурса была не меньше той суммы, которую предприятие может получить при переработке сырья в готовую продукцию.

Запишем это условие отдельно для каждого вида продукции:

a₁₁y₁ + a₂₁y₂ + …+ a_m1y_m ≥ c₁,- для первого вида продукции (выручка от продажи сырья, необходимого для производства единицы продукции первого вида, должна быть больше или равна прибыли от реализации единицы продукции первого вида)

a₁₂y₁ + a₂₂y₂ + …+ a_m2y_m ≥ c₂, - для второго вида продукции

………………………………

a_1ny₁ + a_2ny₂ + …+ a_mny_m ≥ c_n, - для n-ого вида продукции.

 

3) В результате учета интересов двух сторон (покупателя и продавца) мы получаем вторую задачу: Найти такой набор цен (оценок) ресурсов Y=(y_1,y₂,…,y_m), при котором общие затраты на ресурсы будут минимальными при условии, что выручка от продажи ресурсов будет не меньше той суммы, которую предприятие может получить при переработке сырья в готовую продукцию.

 

Цены ресурсов y₁,y₂,…,y_m  в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены, определяемые в результате решения задачи. Поэтому их чаще называют оценками ресурсов.

 

Взаимно-двойственные задачи линейного программирования и их свойства

Рассмотрим формально две задачи I и II линейного программирования, представленные выше в таблице.

Обе задачи обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой – минимум.

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

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «<=», а в задаче минимизации – все неравенства вида «>=».

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

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

6. Условия неотрицательности переменных имеются в обеих задачах.

 

Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем мы будем называть их просто двойственными задачами.

 

Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи:

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду «<=», а если минимум – к виду «>=». Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2. Составить расширенную матрицу А₁, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Найти матрицу А₁^`, транспонированную к матрице А_1.

4. Сформулировать двойственную задачу на основании полученной матрицы А₁^` и условия неотрицательности переменных.

Пример.

F = -7х₁ + 2х₂ → max

При ограничениях

-3х₁ + 5х₂ ≥ 1,

   -х₁ + 4х₂ ≤ 24

     х₁ - х₂ ≥ 6

х₁, х₂ ≥ 0

Решение:

1. Т.к. исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду ≤, для чего обе части первого и третьего неравенства умножим на «-1». Получим

3х₁ - 5х₂ ≤ - 1,

   -х₁ + 4х₂ ≤ 24

    - х₁ + х₂ ≤- 6

2. Составим расширенную матрицу системы

          -7   2  F

3. Найдем матрицу А₁^`, транспонированную к А.