Двойственность в линейном программировании. Теория двойственности в линейном программировании

Основные утверждения о взаимно двойственных задачах содержатся в следующих теоремах.

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

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

Вторая теорема двойственности. Для того, чтобы два допустимых решения
иУ =(у 1 , у 2 , …, у m ) пары двойственных задач были оптимальными необходимо и достаточно, чтобы они удовлетворяли так называемым «условиям дополняющей нежесткости»:

1)

2)

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

Третья теорема двойственности (теорема об оценках). Значения переменныху i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов ограничений исходной задачи на экстремальное значение ее целевой функции Z max , т.е.

.

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

В разделе 3.1 приведен один из возможных вариантов экономической интерпретации двойственных задач. В случае рассмотрения задачи планирования работы предприятия, производящего n видов продукции с использованиемm видов ресурсов, решением исходной задачи является план производства
, а решением двойственной задачи – совокупность цен (двойственных оценок) ресурсовУ =(у 1 , у 2 , …, у m ), соответствующих этому плану.

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

Согласно третьей теореме двойственности оценки ресурсовУ =(у 1 , у 2 , …, у m ) выступают как мера влияния объемов ресурсов на величину максимума товарной продукции (Z max ). Они показывают: на сколько увеличится значение целевой функции при приращении данного ресурса наединицу . Следовательно, еслиi -й ресурс увеличится на
единиц, то целевая функция соответственно возрастет на
ден. ед. Однако надо помнить, что это справедливо только для таких приращений ресурса, которые не вызовут изменение базиса исходной задачи.

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

для коэффициентов
.

Пример расчета предела увеличения ресурса для задачи 2.1 приведен в разделе 2.2. В этой задаче при увеличении ресурса 2, не превышающем 6000 ед., справедлива его оценка y 2 , являющаяся решением двойственной задачи.

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

.

Из второй теоремы двойственности следует, что если оценкау i единицы ресурса положительна, то при оптимальном плане производства этот ресурс используется полностью, т.е. является по определению дефицитным, ау i называетсястепенью дефицитности . Если же ресурс используется не полностью, то его оценка равна0. Аналогично, еслиj -я продукция используется в производстве, т.е.
, то она в оптимальных двойственных оценках неубыточна (рентабельна), если же она убыточна (нерентабельна), то в производстве не используется (
). Двойственная оценкау j такой продукции называетсястепенью нерентабельности .

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

Решение двойственной задачи получается в последней симплексной таблице исходной задачи (3.1)-(3.3), в (М+1)-й строке.

Если в качестве исходной задачи служит модель (3.4)-(3.6), то решение двойственной к ней (3.1)-(3.3) получается умножением на (-1) соответствующих элементов (М+1)-й строки последней симплекс-таблицы задачи (3.4)-(3.6).

Для того чтобы правильно выписать из симплекс-таблицы решение двойственной задачи, необходимо установить соответствие переменных прямой и двойственной задач, исходя из их канонической формы:

– основным переменным прямой задачи соответствуют дополнительные переменные двойственной;

– дополнительным переменным исходной соответствуют основные переменные двойственной модели.

Значения основных переменных двойственной задачи расположены в столбцах дополнительных переменных (М+1)-й строки симплекс-таблицы прямой задачи, а значения дополнительных переменных – в столбцах основных переменных той же строки.

Рассмотрим оптимальный план задачи 2.1 (таблица 3.1).

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

В таблице 3.1 скопирована последняя симплекс-таблица задачи 2.1 и подписаны обозначения двойственных переменных, значения которых получаются одновременно с решением исходной задачи.

Таблица 3.1 – Расположение оптимального плана двойственной

задачи в симплекс-таблице исходной модели

Оптимальный план:

,
,
.

,
,
,

.

Оптимальный план двойственной задачи:

,
,
,

,

.

.

Именно по двойственным переменным был проведен экономический анализ решения задачи линейного программирования в разделе 2.2.

Введение
Под двойственной задачей понимается вспомогательная задача линейного программирования , формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.
Целью курсового проекта является изучить литературу по выбранной теме и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования , а также решить двойственную задачу линейного программирования с помощью программы MS Excel .
Курсовой проект состоит из введения, двух глав и заключения.
В первой главе рассматриваются основные понятия и предложения теории двойственности ЗЛП, виды математических моделей двойственных задач и их экономическая интерпретация.
Во второй главе рассматривается решение двойственной задачи с помощью программы MS Excel.

1. Двойственность в линейном программировании
1.1 Прямые и двойственные задачи линейного программирования
С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов , чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C j минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции x j (j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2,…, n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования , состоящей, как мы уже знаем, в нахождении максимального значения функции :
F=c 1 x 1 +c 2 x 2 +…c n x n
при условиях

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.
2. Матрица

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

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).
3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.
5. Если переменная x j исходной задачи может принимать только лишь положительные значения, то j -е условие в системе двойственной задачи является неравенством вида «>». Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i – соотношение в системе исходной задачи является неравенством, то i -я переменная двойственной задачи . В противном случае переменная у j может принимать как положительные, так и отрицательные значения.
Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой задачи и соотношения двойственной задачи являются неравенствами вида « «. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.
Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты C j функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.
Рассмотрим задачу использования ресурсов. У предприятия есть t видов ресурсов в количестве b i (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции
Z=C 1 x 1 +C 2 x 2 + … +C n x n

Определим ресурсы , которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через у i (j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.
1.2 Основы теоремы двойственности
1.2.1. Несимметричные двойственные задачи

Теорема двойственности:

1.2.2 Симметричные двойственные задачи

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

Допустим, что q 0j =min(x i /x ij)=0, т.е. x i =0, тогда x ij выбирается как разрешающий элемент, но лишь тогда, когда x ij >0.
Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Пока не будет получено Х>0, процесс не прекращается.
Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи.
Используя при решении, алгоритм двойственного симплексного метода условие Z j –C j >0 допускается не учитывать, пока не будут исключены все х i <0.
Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все х i <0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q 0j =max(x i /x ij)>0.
Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.

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


Рис. 2
Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b 1 ,…, b i ,…, b m ); внизу каждого столбца - цена продуктов (с 1 ,…, с j ,…, с m ).
В каждой клеточке матрицы записаны так называемые технологические коэффициенты a ij , показывающие расход i -го ресурса на производство единицы j -го продукта.
Запишем конкретный числовой пример

Рис. 3

2.2 Построение математической модели
Теперь приступим к созданию математической модели, т.е. к математической записи задачи.
Целевая функция:

Ограничения:

x 1 ³ 0;
x 2 ³ 0;
x 3 ³ 0.
2.3 Описание решения данной задачи
Решим поставленную выше задачу с применением EXCEL.

Содержание ячеек:
B1:D1 – имена продуктов (технологических способов);
A2:A4 – имена ресурсов;
B2:D4 – технологические коэффициенты (расход ресурсов при единичных интенсивностях технологических способов);
B6:D6 – цены продуктов;
B8:D8 – переменные;
F2:F4 – запас ресурсов;
G2:G4 – плановые расходы ресурсов, получаются в результате решения;
G6 – значение целевой функции, получается в результате решения.
Формулы для вычислений:
G2=СУММПРОИЗВ (B$8:D$8; B2:D2);
G3:G4 – копируются из G2;
G6=СУММПРОИЗВ (B8:D8; B6:D6).
Запишем формулы в ячейки G2:G4. Установить курсор на G2. На панели инструментов выбрать значок формул (f ). Появятся два окна. В окне «категория» выбрать «математические», затем в окне «функция» выбрать «СУММПРОИЗВ». Появится окно «СУММПРОИЗВ». В нем нужно указать, где располагаются операнды. Первый операнд – строка B$8:D$8, второй операнд – стока B2:D2. В ячейки G3:G4 формулу скопировать из G2. Аналогичным образом записать формулу целевой функции в ячейку G6. Теперь нужно указать остальные условия решения задачи. Установить курсор на ячейку целевой функции G6. В главном меню выбрать «сервис», а потом «поиск решения». Появится окно, в котором нужно указать:
1. Целевая ячейка – G6;
2. Включить кнопку «максимальное значение»;
3. Указать изменяемые ячейки (расположение переменных) – B8:D8;
4. Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:
G2:G4 F2:F4 – плановый расход ресурсов меньше их запаса.
Теперь электронная модель сформирована и можно решать задачу. Для этого нужно вернуться в окно «поиск решения» и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Результаты, Устойчивость , Пределы .

Рис. 4.1.4
Основные результаты видны в таблице (рис. 4.1.4.). По сравнению с условиями задачи, показанными на рис. 4.1.3., появились данные:
1. Значение целевой функции в ячейке G6 = 15880;
2. Значения переменных в ячейках B8:D8: х 1 = 86, х 2 = 0, х 3 = 268; это значит, что 1-й продукт должен производиться в объеме 86 единиц, 2-й – 0, а 3-й – 286.
3. Плановый расход ресурсов в ячейках G2:G4: расход 1-го ресурса = 271,6, расход 2-го ресурса = 310, расход 3-го ресурса = 2200.
Как видно 1-й ресурс недоиспользован, а 2-й и 3-й израсходованы полностью.
Кроме результатов в электронной таблице EXCEL готовит три отчета: Результаты, Устойчивость, Пределы. Отчет по результатам изображен на рис 4.1.5, где изображены три таблицы.
Отчет по результатам
Целевая ячейка (максимум)
$G$6 Цены ЦФ 15880
Изменяемые Ячейки

Заключение

Список используемой литературы

1.6.1. Понятие двойственной задачи ЛП . Пусть задана КЗЛП (1.7). Если целевая функция f (x ) = cx достигает макси­мального значения на множестве D , то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m -мерный вектор, то

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с . Тогда при любых х ≥ 0 справедливо неравенство

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

F Если задана каноническая задача ЛП

то задача ЛП

называется двойственной по отношению к ней. Соот­ветственно, задача (D, f ) no отношению к

(D*,f *) назы­вается прямой (или исходной).

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

F Если задана общая задача ЛП

f (x ) = c 1 x 1 + ... + с j х j + с j +1 х j+ 1 + ... + с n x n → max, x Î D, (1.50)

где D определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется об­щая задача ЛП

где D* определяется системой уравнений и неравенств:

Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.

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

1. Тип оптимума меняется на противоположный, т. е. макси­мум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец огра­ничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х j ≥ 0 или u j ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (a j u ≥ с j или a i x ≤ b j ).

5. Множество номеров ограничений, имеющих форму нера­венств в прямой задаче (например, a i x ≤ b j или a j u ≥ с j) , опреде­ляют множество индексов переменных, на которые накладыва­ется условие неотрицательности, в двойственной задаче (u i ≥ 0 или x i ≥ 0).

F F Из приведенного определения вытекает важное свой­ство - симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей :

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

В матричной форме пара двойственных общих задач линей­ного программирования может быть кратко записана как:

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D , f ):

тогда двойственной к ней будет задача (D* , f* ):

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

Доказательство.

Достаточно доказать теорему для случая, когда задача (D , f ) является канонической. Рассмотрим пару двойственных задач

Из того, что вектор и является допустимым планом задачи (D *, f *), следует, что иА ≥ с . Умножив левую и правую части дан­ного неравенства на вектор х ≥ 0 , получим равносильную сис­тему неравенств

Одновременно для вектора х, являющегося допустимым планом задачи (D, f ), справедливо равенство Ax=b . Тем самым доказа­но, что иb ≥ сх. A

Замечание. Теорема 1.4, разумеется, верна и для оптималь­ных планов взаимно двойственных задач: f(x*) ≤ f*(u*), где х* и u*- любые оптимальные планы задач (D, f ) и (D*,f *). На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*).

Доказательство.

Согласно теореме 1.4, для всех допустимых планов х задачи (D, f ) справедливо неравенство сх < b . По условию теоремы f()=f() или, что то же самое, с = b . Следовательно, верно утверждение: для любого x Î D с >сх , т. е. х является опти­мальным планом для задачи (D, f ).

Рассуждения, доказывающие оптимальность плана для за­дачи (D* ,f *), проводятся аналогично. A

Доказательство.

Если предположить, что у двойственной задачи (D *,f *) су­ществует хотя бы один допустимый план и̃ , то, согласно теоре­ме 1.4, для любого допустимого плана х задачи (D, f ) справед­ливо неравенство f(x) ≤ f *( ) <+∞. Последнее означает, что целевая функция f задачи (D, f ) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о сущест­вовании допустимых планов двойственной задачи (D*,f *) не­верно. A

Следующее утверждение, известное как теорема равнове­сия , используется при проверке оптимальности планов ЗЛП.

Доказательство.

Векторы х* и и*, будучи допустимыми планами соответствую­щих задач, удовлетворяют условиям: Ах* = b , х* > 0 и и*А-с ≥ 0 . Найдем скалярное произведение

Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u*b=сх*. Последнее означает, что (u*А-с)х* = 0 . Однако ска­лярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные про­изведения их соответствующих координат равны нулю. Следо­вательно, если x j * > 0, то u*а j – с j = 0, если же x j = 0, то возмож­но u*а j – с j ≥ 0 , что и утверждается в теореме. A

Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область до­пустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая име­ет только две переменные.

Еще раз вернемся к таблице Т 2 ( q ) (рис. 1.8 ), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ -1 (β ( q )), для которой было введено обозначение δ 0 (β ( q )). По­элементно она может быть записана в следующем виде:

Введем вектор = (δ 0,1 (β (q )), δ 0,2 (β (q )),..., δ 0,m (β (q ))). Нетруд­но проверить, что строка оценок a 0 (β ( q )) может быть представ­лена следующим образом:

Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũА≥с . Следовательно, век­тор и является допустимым планом двойственной задачи.

В то же время элемент b 0 (β ( q )), содержащий текущее значе­ние целевой функции и равный на последней итерации f(x*), до­пускает представление

Согласно теореме 1.5 из равенства f (х* ) = f *(ũ ) вытекает, что вектор ũ служит оптимальным планом двойственной задачи: u = ũ.

Окончательно можно утверждать, что для оптимального базиса

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

Читателю в качестве самостоятельного упражнения предла­гается построить задачу, двойственную к (1.34)-(1.35), реше­ние которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2), полученный в таблице Т 2 (3) , является для нее допустимым и оптимальным планом.

1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП бази­руется на модели простейшей задачи производственного планирования , описанной во введении. Напомним, что в ней каждый (j -й) элемент вектора х рассматривается как план вы­пуска продукции данного вида в натуральных единицах, с j - цена единицы продукции j -го вида, а j - вектор, определяющий технологию расходования имеющихся m ресурсов на производ­ство единицы продукции j -го вида, b - вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых значений A, b и с найден оптимальный план х* , максимизирующий суммарный доход max{cx }=cx *. Достаточно естественным представляется во­прос: как будет изменяться оптимальный план х * при измене­нии компонент вектора ограничений b и, в частности, при ка­ких вариациях b оптимальный план х * останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчи­вости х * имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов b i ; могут существенно колебаться после принятия планового решения х *.

Когда вектор ограничений b изменяется на Δb или, как еще говорят, получает приращение Δb , то возникают соответству­ющие вариации для оптимального плана х*(b+ Δb) и значения целевой функции f(х *(b+ Δb )). Допустим, приращение Δb та­ково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+ Δb) ≥0. Определим функцию F (b ), возвраща­ющую оптимальное значение целевой функции задачи (D (b ), f ) для различных значений вектора ограничений b

Рассмотрим отношение ее приращения F(b+ Δb)-F(b) к при­ращению аргумента Δb . Если для некоторого i устремить Δb i → 0, то мы получим

Учитывая, что в соответствии с теоремой 1.5

и подставив (1.57) в (1.56), приходим к выражению

F F Из формулы (1.58) вытекает экономическая интерпре­тация оптимальных переменных двойственной зада­чи . Каждый элемент u i * может рассматриваться как предель­ная (мгновенная) оценка вклада i -го ресурса в суммарный доход F при оптимальном решении х *. Грубо говоря, величи­на u i * равна приросту дохода, возникающему при увеличе­нии ресурса i на единицу при условии оптимального ис­пользования ресурсов.

В различных источниках компоненты оптимального плана двойственной задачи также называются двойственными оцен­ками или теневыми ценами , а Л. В. Канторович предлагал та­кой термин, как объективно обусловленные оценки.

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

F F Если при использовании оптимального плана прямой за­дачи i-e ограничение выполняется как строгое неравен­ство, то оптимальное значение соответствующей двой­ственной переменной равно нулю, т.е. если

В рамках рассматриваемой задачи производственного плани­рования это означает, что если некоторый ресурс b i , имеется в избыточном количестве (не используется полностью при реа­лизации оптимального плана), то i -e ограничение становится несущественным и оценка такого ресурса равна 0.

F F Если при использовании оптимального плана двойствен­ной задачи j-e ограничение выполняется как строгое не­равенство, то оптимальное значение соответствую­щей переменной прямой задачи должно быть равно нулю, т. е. если a 1, j u 1 * +...а m , j и m – с j > 0, то х j * = 0.

Учитывая экономическое содержание двойственных оценок u 1 *,...,u m , выражение а 1, j u 1 * +…a m , j u m * может быть интерпретиро­вано как удельные затраты на j -й технологический процесс. Сле­довательно, если эти затраты превышают прибыль от реализа­ции единицы j -го продукта, то производство j -го продукта является нерентабельным и не должно присутствовать в опти­мальном производственном плане (x j * =0).

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

1.6.5. Анализ параметрической устойчивости реше­ний ЗЛП . В предыдущем пункте мы затронули некоторые ас­пекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b . Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции с j , j Î1:n .

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

Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допусти­мых планов D некоторой задачи ЛП. Как видно из рисунка, це­левая функция f (ее поведение отражает линия уровня, пока­занная жирным пунктиром) достигает экстремального значе­ния в точке х *, а изменению ее коэффициентов от с к с" или с" на рисунке соответствует поворот линии уровня относительно х *. Активным, т. е. обращающимся в равенство, ограничениям в точке х * соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с , линия уровня целе­вой функции не выходит за пределы образуемого линиями огра­ничений конуса, х* остается оптимальным планом. Как показа­но на рис. 1.10 , этот план не меняется при переходе от с к с" , и, наоборот, при переходе от с к с" линия уровня целевой функции f(x)=c"x пересечет линию (2), что вызовет изменение опти­мального базисного плана, которым теперь станет точка .

Используя условия оптимальности плана ЗЛП

нетрудно получить количественные оценки для пределов коле­баний коэффициентов целевой функции, при которых не проис­ходит изменение оптимального плана. Допустим, вариации под­вергся некоторый элемент с r : с r ′ = с r + ε r . Возможны два случая:

1. Столбец r не входит в оптимальный базис (r Î N (β ( q ))). Тог­да для неизменности оптимального плана необходимо и доста­точно выполнение условия

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

2. Столбец r входит в оптимальный базис (r Î N (β ( q ))). В этом случае для сохранения оптимальности текущего плана потре­буется выполнение для всех небазисных столбцов (j Ï N (β ( q ))) условий

Следовательно, в этом случае допустимая вариация должна удовлетворять условиям

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

2. Теория двойственности в линейном программировании. Двойственный симплекс-метод

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

2.1. Определение и экономический смысл двойственной ЗЛП

Пусть прямая задача записана в каноническом виде:

https://pandia.ru/text/78/450/images/image005_76.jpg" width="23" height="25 src=">целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а векторправой части прямой задачи - вектором це­левой функции двойственной задачи.

5) Если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется, а ограничения имеют вид, и наоборот.

Прямая задача Двойственная задача

Пример 2.1. Составить задачу,двойственную следующей задаче:

при ограничениях:

Решение.

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

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

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

4. Сформулируем двойственную задачу:

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

6.1. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов

Ранее была рассмотрена задача об использовании ресурсов (эконо­мико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1)..jpg" width="48" height="23">- число единиц ресурса, потребляемого при производстве едини­цы продукции https://pandia.ru/text/78/450/images/image024_16.jpg" width="16" height="24 src=">- прибыль (выручка) от реали­зации единицы продукции (или цена продукции).

Предположим, что некоторая организация решила закупить ресурсы https://pandia.ru/text/78/450/images/image027_10.jpg" width="95" height="24">заинтересована в том, чтобы затраты на все ресурсы Z в количествахпо ценам соответственнобыли минимальны, т. е

Готовая продукция" href="/text/category/gotovaya_produktciya/" rel="bookmark">готовую продукцию . На изготовление единицы про­дукции P1 расходуется единиц ресурса , единиц ресурса единиц ресурса , ..., единиц ресурса по цене соответственно Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изго­товлении единицы продукции P1, должны быть не менее ее цены с1, т. е.

https://pandia.ru/text/78/450/images/image040_4.jpg" width="113" height="20 src=">. Экономико-математическая модель и содержательная интерпретация полученной та­ким образом двойственной задачи II приведены в правой части табл. 6.1.

Цены ресурсов в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, "ненастоящие" цены..jpg" width="113" height="25 src=">являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их ча­ще называют оценками ресурсов.

2.2. Основные положения теории двойственности

https://pandia.ru/text/78/450/images/image048_0.jpg" width="47" height="37 src=">- планы соответственно прямой и двойственной ЗЛП, тогда

(2.12)

Теорема 2, Пусть- планы соответственно прямой и двойственной ЗЛП и

, тогдаhttps://pandia.ru/text/78/450/images/image051_0.jpg" width="195" height="32"> (2.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

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

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

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

3. Целочисленные модели исследования операций

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

Задача называется полностью целочисленной, если условие целочиc-ленности на­ложено на все ее переменные; когда это условие относится лишь к некоторым перемен­ным, задача называется частично целочисленной. Если при этом целевая функция и функ­ции, входящие в ограничения, линейные, то задача является линейной целочисленной.

Значительная часть экономических задач , относящихся к задачам линейного про­граммирования, требует целочисленного решения. К ним относятся задачи, у которых пе­ременные величины означают количество единиц неделимой продукции, например, рас­пределение производственных заданий между предприятиями, раскрой материалов, загрузка оборудования, распределение судов по линиям, самолетов по рейсам, а также за­дачи по производству неделимой продукции. Если единица составляет малую часть всего объема производства, то оптимальное решение находят обычным симплексным методом, округляя его до целых единиц, исходя из смысла задачи. В противном случае округление может привести к решению, далекому от оптимального целочисленного решения.

Пример 3,2, В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19,3 м площади. На приобретение оборудования предприятие может израсходовать 10 тыс. у. е., при этом оно может купить оборудование двух видов. Комплект оборудования 1 вида стоит 1000 у. е., а II вида - 3000 у. е. Приобре­тение одного комплекта оборудования 1 вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида - на 3 ед. Зная, что для установки одного комплекта оборудования 1 вида требуется 2 м2 площади, а оборудования II вида - 1https://pandia.ru/text/78/450/images/image053_0.jpg" width="19" height="17 src=">комплектов оборудования 1 вида икомплектов оборудования II ви­да. Тогда переменныеидолжны удовлетворять следующим неравенствам:

(3.11)

Если предприятие приобретет указанное количество оборудования, то общее уве­личение выпуска продукции составит

(3.12)

По своему экономическому содержанию переменные х\ и Х2 могут принимать лишь целые неотрицательные значения, т. е.,

(3..jpg" width="55" height="29 src=">, максимизирующий линейную форму

(З.1)

и удовлетворяющий условиям:

https://pandia.ru/text/78/450/images/image064_0.jpg" width="22" height="30 src=">- целочисленная переменная, значе­ниекоторой в оптимальном решении ослабленной задачи является дробным. Интервал

не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значениедолжно удовлетворять одному из неравенств

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

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

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

3.2. Задача коммивояжера

Имеется n городов, занумерованных числами 1,2,...,n..jpg" width="64" height="20">между ними..jpg" width="37" height="18 src=">- время переналадки при переходе от обработки детали i к обработке детали j . Требуется найти после­довательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программи­рования определим булевы переменные следующим образом: , если коммивояжер переезжает и i-го города в j-й; https://pandia.ru/text/78/450/images/image075.jpg" width="33" height="28 src=">удовлетворяющих следующим соотношениям:

Водохранилище" href="/text/category/vodohranilishe/" rel="bookmark">водохранилищах и многими другими. Кроме того, модель можно видоизменить, с тем чтобы она учитывала перевозку нескольких видов продукции.

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

В классической транспортной задаче рассматриваются перевозки (прямые или с промежуточными пунктами) одного или нескольких видов продукции из исходных пунк­тов в пункты назначения. Эту задачу можно видоизменить, включив в нее ограничения сверху на пропускные способности транспортных коммуникаций . Задачу о назначениях и задачу управления запасами можно рассматривать как задачи транспортного типа.

Рассмотрим построение экономико-математической модели транспортной задачи на примере.

Пример 4.1. Построить экономико-математическую модель следующей задачи. Имеются три поставщика и четыре потребителя. Мощ­ность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары "поставщик - потре­битель" сведены в таблицу поставок (табл. 7.1).

https://pandia.ru/text/78/450/images/image078.jpg" width="33" height="19">-клетки (i - номер

строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i-го поставщика

https://pandia.ru/text/78/450/images/image080.jpg" width="491" height="79 src=">

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу).

На множестве неотрицательных решений системы ограничений (7.1) и (7.2) найти такое решениеhttps://pandia.ru/text/78/450/images/image082.jpg" width="17" height="18 src=">.jpg" width="16" height="17 src=">в количестве единиц. Известна стоимость cij перевозки еди­ницы груза от i-ro поставщика к j-му потребителю.

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

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

1. Если целевая функция f исходной задачи максимизируется, то целевая функция z двойственной - минимизируется, и наоборот.

2. Количество ограничений (m ) исходной задачи равно количеству переменных двойственной, а количество переменных (n ) исходной равно количеству ограничений двойственной. Переменные двойственной задачи обозначим через .

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

4. Каждой переменной неограниченной по знаку, соответствует ограничение вида «=» двойственной задачи, и наоборот.

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

6. Матрица А коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспонируется .

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

Таблица 16

Исходная задача	Двойственная задача
Максимизация f Количество ограничений m Переменные x j ³0 i -е ограничение вида «£» х j не ограничено по знаку i -е ограничение вида «=» Свободные члены ограничений b i Коэффициенты при x j в целевой функции (c j ) Матрица коэффициентов при неизвестных в ограничениях (А )	Минимизация z Количество ограничений n Переменные j-е ограничение вида «³» y i ³0 j -е ограничение вида «=» не ограничено по знаку Коэффициенты при y i в целевой функции (b i ) Свободные члены ограничений (c j ) Транспонированная матрица коэффициентов при неизвестных в ограничениях (A T )

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

Двойственная к этой задаче будет иметь вид:

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

В таблице 17 приведены частные виды исходных задач линейного программирования в матричном виде и соответствующие им двойственные задачи. Через обозначена матрица - строка неизвестных двойственной задачи.

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

Первые две пары взаимно двойственных задач в таблице 17 называются симметричными, вторые две - несимметричными из-за наличия ограничений вида «=».

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

Таблица 17

Пример

Чтобы построить двойственную задачу, исходную необходимо привести к форме (I) путем умножения обеих частей второго ограничения на (–1). После этого преобразования исходная задача примет вид:

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

Пример : Построить задачу, двойственную к данной:

Для построения двойственной задачи воспользуемся формами (II), (IV) и преобразуем данную задачу путем умножения обеих частей второго неравенства на (–1). Тогда исходная задача будет иметь вид:

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

Используя пример, поясним некоторые правила построения двойственных задач. Поскольку количество ограничений исходной задачи m =3, двойственная задача должна иметь три переменные: Количество переменных исходной задачи n =4, поэтому двойственная должна иметь четыре ограничения. Переменные x 1 и x 4 исходной задачи не ограничены по знаку. В силу этого первое и четвертое ограничения двойственной задачи имеют вид равенств. Третье ограничение исходной задачи имеет вид равенства, следовательно, переменная y 3 двойственной задачи не ограничена по знаку.

Контрольные вопросы и упражнения

1. Что представляет собой двойственная задача линейного программирования?

2. В чем отличие симметричных задач двойственной пары от несимметричных?

3. Постройте задачи, двойственные к данным:

4. Дайте экономическую интерпретацию задачи, двойственной к задаче использования ресурсов.

5. Какая задача из пары взаимно двойственных задач может быть принята в качестве исходной и какая в качестве двойственной? Какие задачи на практике считают двойственными?

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

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

8. Постройте задачу, двойственную к данной:

Решите исходную и двойственную задачи графическим методом.

9. Постройте задачи, двойственные к данным:

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

10. Как по решению исходной задачи найти решение двойственной и наоборот?