Материал: Математические методы и модели в экономике. Амелин С.В

Тогда двойственная задача по отношению к задаче (4.17) – (4.20) состоит в нахождении минимального значения функции:

Правила составления двойственной задачи:

1. Если функция исходной задачи 4.17 – 4.20 задается на максимум, то целевая функция двойственной к ней задачи (4.21) – (4.24) задается на минимум.

2. Матрица

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

95

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

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

Связь между решениями прямой и двойственной задачи

Лемма 1. Если Х – некоторый план исходной задачи (1.17) – (1.20), а Y – произвольный план двойственной задачи (1.21) – (1.24), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.

f(x) F(Y).

Лемма 2. Если f(x*) = F(Y*) для некоторых планов Х*

и Y* задач (1.17) – (1.20) и (1.21) – (1.24), то Х* - оптималь-

ный план исходной задачи, Y* - оптимальный план двойственной задачи.

Теорема двойственности. Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т.е.

max f(x) = min F(Y).

Если целевая функция одной из пары двойственной задач не ограничена (для f(x) – сверху, для F(Y) – снизу), то другая задача вообще плана не имеет.

Экономическая интерпретация двойственных задач

Пример. Для производства трех видов изделий А, В и С используются три различных вида сырья, запасы которого составляют соответственно 180, 210 и 244 кг. Нормы затрат сырья на единицу продукции и доход от реализации единицы продукции приведены в табл. 4.6.

96

а суммарные оценки сырья, используемого на производство единицы продукции каждого вида, должны компенсироваться доходом от реализации единицы продукции данного вида:

4y1 + 3y2 + y3 10,

2y1 + y2 + 2y3 14, (4.29) y1 + 3y2 + 5y3 12,

Задачи (4.25) – (4.27) и (4.28) – (4.30) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий А, В и С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий.

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

m

аij yi = Cj если Хj > 0;

i 1

m

аij yi > Cj если Хj = 0.

i 1

98

Решение задач линейного программирования симплекс-методом

Если условия задачи линейного программирования не противоречивы, то область ее допустимых решений образует выпуклый многогранник в n-мерном пространстве (многоугольник для двух переменных). При этом оптимальное решение, если оно существует, обязательно достигается в некоторой вершине многогранника (возможно, и более чем в одной).

Таким образом, чтобы найти решение задачи линейного программирования, достаточно перебрать лишь планы, соответствующие вершинам многогранника допустимых решений. Такие планы называют опорными. Однако в сложных задачах и число вершин может оказаться чрезмерно большим, вследствие чего нахождение всех опорных планов потребует огромного объема вычислений.

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

Симплекс-метод применяется к задаче, записанной в канонической форме (используем одну из двойственных задач линейного программирования):

f(x) = 10Х1 + 14Х2 + 12Х3 + 0 Х4 + 0 Х5 + 0 Х6 max,

Для решения задачи линейного программирования составим симплексную таблицу (рис. 49).

99