Двойственная задача линейного программирования Теоремы двойственности и их экономическая интерпретация

Рассмотрим задачу линейного программирования следующего вида:

(1)целевая ф-я

(2)

В задаче требуется максимизировать целевую функцию;Двойственная задача линейного программирования имеет вид

(3) и (4)соотв

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

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

Экономическая интерпритация. Пусть в качестве управляющих переменных xj, исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами bi, – количество ресурсов i-го типа, используемых для изготовления изделий. Через aij обозначено количество ресурсов i-го типа, идущее на изготовление одного изделия j-го вида, (j – прибыль от реализации одного изделия j-го вида). Тогда исходная модель соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль. Пусть предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через цены на единицу ресурсов i-го вида, Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они нe должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой (3), второе условие – ограничениями (4). В левой части каждого из неравенств (4) стоит прибыль от продажи ресурсов всех типов, идущих на изготовление j -го изделия, в правой части – прибыль от продажи j-го изделия, Таким образом, двойственная задача (3) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов.

18.Транспортная задача.Метод севево-западного угла.Заполнение клеток начинается с верхней леовй клеточки(11клетка).Перевозка( 11)заполняется с мах удовлетворением либо поставщика.,либо потрибителя.При заполнении некоторой клетки кроме последней вычеркивается или одна строка или только один столбец.Лишь при заполнении последней строки столбец и строка зачеркивается полностью.Если при заполнении некоторой клетки отличн от последней полностью были удовлетв и поставщику и потреб. Полностью вычеркивается строка либо столбец а незанятые клетки ставится 0.По методу северо-западного угла удовлетв.всегда верхний-левый угол из невырежденных.Основное приимущество:его простота.Недостаток:не учитываются стоимости перевозок.

21.Постановка и экономико-математическая модель открытой транспортной задачи.

Имеется m пунктов производства однородного продукта с объемами производства A1,A2,…,Am. Имеется n пунктов потребления этого продукта с объемами потребления b1,b2,…,bn. Известны оценки С= (Cij) M*N транспортных затрат на перевозку единицы груза от i-того поставщика к j-тому потребителю (по коммуникации от i к j). Надо так прикрепить потребителей к поставщикам, чтобы минимизировать суммарные транспортные затраты на перевозку груза. ЭММ ТЗ: Обозначим через Xij, i=1,m j=1,n объемы перевозок по коммуникации i→j, т.е. в рассмотрение вводится матрица X=(Xij)m*n.

Min ∑ ∑ Cij Xij

∑ Xij = Ai, i=1,m

∑ Xij = Bj, j=1,n

Если не выполняются условия баланса между спросом и предложением ∑Ai = ∑Bj, то ТЗ называется открытой, при этом могут быть 2 случая. 1 случай:∑Ai > ∑Bj, тогда ограничения имеют вид ∑ Xij ≤ Ai, i=1,m. 2 случай:∑Ai < ∑Bj. Тогда ограничения имеют вид ∑ Xij ≤ Bj, j=1,n