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

 

     Дадим геометрическую интерпретацию элементов  этой задачи. Каждое из ограничений (12), (13) задает на плоскости  некоторую полуплоскость. Полуплоскость выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (11) (13) есть выпуклое множество.

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

     Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (11)Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

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

     Частная производная (14) ((15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, - скорости возрастания Z соответственно вдоль осей . Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции

     Вектор - c указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямым семейства

     Из  геометрической интерпретации элементов  ЗЛП вытекает следующий порядок ее графического решения:

1. С  учетом системы ограничений строим область допустимых решений

2. Строим  вектор  наискорейшего возрастания целевой функции вектор градиентного направления.

3. Проводим  произвольную линию уровня 

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

5. Определяем  оптимальный план  и экстремальное значение целевой функции  

1.3 Симплексный метод. 

     Общая идея симплексного метода (метода последовательного  улучшения плана) для решения ЗЛП состоит:

1) умение  находить начальный опорный план

2) наличие  признака оптимальности опорного  плана

3) умение  переходить к нехудшему опорному плану. [2,13]

Пусть ЗЛП представлена системой ограничений  в каноническом виде –

     Говорят, что ограничение ЗЛП имеет  предпочтительный вид, если при неотрицательной  правой части  левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

     Пусть система ограничений имеет вид:

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

которая имеет предпочтительный вид -

     В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю

     Пусть далее система ограничений имеет  вид 

     Сведём  её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

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

     Пусть исходная ЗЛП имеет вид:

причём  ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

     Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид:

     Если  некоторые из уравнений (2) имеют  предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

М-задачи (4)-(6) все искусственные переменные , то план является оптимальным планом исходной задачи (1)-(3).

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

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

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

Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

3.1 Признаки  оптимальности.

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

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

1.4 Понятие двойственности. 

     Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах единиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозначим через норму расхода сырья i-го вида на единицу j-й продукции, - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи: объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.

Математическая  модель задачи

     Предположим далее, что с самого начала при  изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их .

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

1) общую  стоимость отходов сырья покупающая  организация стремится минимизировать

2) предприятие  согласно уступить отходы только  по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство. [14,12]

     Эти требования формализуются в виде следующей ЗЛП.

     Требование 1 покупающей организации минимизация покупки

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

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

     По  смыслу задачи оценки не должны быть отрицательными:

Переменные  называют двойственными оценками или объективно обусловленными оценками.

     Задачи (1)-(3) и (4)-(6) называют парой взаимно  двойственных ЗПЛ. 

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

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

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

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

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

5. Если  прямая задача на максимум, то  ее система ограничений представляется в виде неравенств типа Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

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

7. Все  переменные в обеих задачах  неотрицательны. [5,23]

Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.

основное  неравенство теории двойственности.

Теорема. (критерий оптимальности Канторовича)

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

Теорема. (малая теорема двойственности)

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

1.5 Основные теоремы двойственности и их экономическое содержание 

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

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