Симметричные двойственные задачи
Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х=(x1, x2,…, xn), которая удовлетворяет системе ограничений
(1.12). АХ>А0, Х>0 и минимизирует линейную функцию Z=СХ
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду. Для этого второе неравенство следует умножить на -1.
Решение двойственной задачи линейного программирования
Необходимо спланировать работу швейной мастерской на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: материал, нитки, пуговицы, труд закройщиков, швей-мотористок и т.д. Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная цена всей продукции (выпуск, выручка) была наибольшей.
|
|
|
Введем следующие обозначения:
i=1,…, m - номера (индексы) используемых ресурсов;
- запас i-го ресурса, т.е. допустимый расход i-го ресурса в плановом периоде; другое название - ограничение по ресурсу i;
j=1,…, n - номера (индексы) продуктов;
- рыночная цена j-го продукта;
- расход i-го ресурса на производство единицы j-го продукта;
- плановый объем производства j-го продукта, величина неизвестная, ее нужно найти в процессе решения задачи. Исходные данные задачи запишем в виде матрицы.
Рис. 2
Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту.
Справа от каждой строки записана величина ограничения по ресурсу (b1,…, bi,…, bm); внизу каждого столбца - цена продуктов (с1,…, сj,…, сm).
|
|
|
В каждой клеточке матрицы записаны так называемые технологические коэффициенты aij, показывающие расход i-го ресурса на производство единицы j-го продукта.
Запишем конкретный числовой пример
Рис. 3
Теперь приступим к созданию математической модели, т.е. к математической записи задачи.
Целевая функция:
Ограничения:
x1 ³ 0;
x2 ³ 0;
x3 ³ 0.
Решим поставленную выше задачу с применением 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. Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:
B8:D8 
0 – неотрицательности переменных;
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
Изменяемые Ячейки
| Ячейка Имя Исходно Результат |
| $B$8 Перем Пр1 0 86 |
| $C$8 Перем Пр2 0 0 |
| $D$8 Перем Пр3 0 268 |
Ограничения
| Ячейка Имя Значение Формула Статус Разница |
$G$2 Рес 1 Расход 271,6 $G$2  $F$2 не связан 228,4
|
| $G$3 Рес 2 Расход 310 $G$3 $F$3 связанное 0
|
| $G$4 Рес 3 Расход 2200 $G$4 $F$4 связанное 0
|
$B$8 Перем Пр1 86 $B$8  0 не связан 86
|
| $C$8 Перем Пр2 0 $C$8 0 связанное 0
|
| $D$8 Перем Пр3 268 $D$8 0 не связан 268
|
Рис. 4.1.5
1-я таблица – целевая ячейка – дает значение целевой функции, которая уже имеется в таблице EXCEL, значит, эти данные избыточны.
2-я таблица – изменяемые ячейки – дает значение переменных, которые уже имеются в таблице EXCEL, эти данные тоже избыточны.
3-я таблица – ограничения – дает оценку ограничений. Колонка «значение» дает значения планового расхода ресурсов и переменных – эти данные имеются в таблице EXCEL и здесь избыточны. Столбец «статус» значением «связанное» отмечает ограничения (не больше или не меньше), которые в результате решения превратились в строгие равенства, прочие ограничения имеют статус «несвязанные». Столбец «разница» показывает, на какую величину ограничения отклонились от строгого равенства. Так, например, ограничение 1-го ресурса 500, плановое значение 271,6, разница = 500 – 271,6 = 228,4.
Отчет по устойчивости изображен на рис. 4.1.6. Он состоит из двух таблиц.
Отчет по устойчивости
Изменяемые ячейки
| Ячейка Имя Результат Норир. Значение градиент |
| $B$8 Перем Пр1 86 0 |
| $C$8 Перем Пр2 0 -22,8 |
| $D$8 Перем Пр3 268 0 |
Ограничения
| Ячейка Имя Результат. Лагранжа значение Множитель |
| $G$2 Рес 1 Расход 271,6 0 |
| $G$3 Рес 2 Расход 310 20 |
| $G$4 Рес 3 Расход 2200 4,4 |
Рис. 4.1.6
Таблица «изменяемые ячейки» показывает значения переменных, которые уже имеются в таблице EXCEL. Столбец «нормируемый градиент» показывает, как влияет увеличение переменных на единицу на величину целевой функции. Таблица «ограничения» содержит важную информацию в столбце «Лагранжа множители». Эти величины в литературе имеют различные названия: объективно обусловленные оценки (О.О.О.) по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем – двойственные оценки и обозначать – vi, где i – номер ограничения. В данном примере v1 = 0, v2 = 20,0, v3 = 4,4. Отчет по пределам показан на рис. 4.1.7.
Отчет по пределам
| Ячейка Целевое Значение имя |
| $G$6 Цены ЦФ 15880 |
| Ячейка Изменяемое Значение имя | Нижний Целевой предел результат | Нижний Целевой предел результат |
| $B$8 Перем Пр1 86 | 0 10720 | 86 15880 |
| $C$8 Перем Пр2 0 | 0 15880 | 0 15880 |
| $D$8 Перем Пр3 268 | 0 5160 | 268 15880 |
Рис. 4.1.7
В этом отчете уже в третий раз дается значение целевой функции 15880, в пятый раз значение переменных (х1 = 86, х2 = 0, х3 = 268). Нижний предел для всех переменных = 0, так, установлены ограничения по переменным. Верхний предел равен соответственно 86, 0 и 268, так устанавливают ограничения по ресурсам. Целевой результат показывает значение целевой функции при соответствующих значениях переменных. Если х1 = 0, то ЦФ = 10720 и т.д.
Запишем математическую модель рассмотренной задачи в общем виде:
Пусть:
В-бюджет, т.е. количество денег, которое можно израсходовать на приобретение ресурсов для производства продукции, а si – рыночная цена i-го ресурса. Тогда единственное ограничение по ресурсам будет выглядеть следующим образом:
.
Смысл этого ограничения - нельзя израсходовать ресурсов на сумму больше, чем В.
Здесь: 
- расход i-го ресурса в натуральном выражении по j-му технологическому способу;
- расход i-го ресурса в натуральном выражении по всем способам;
- суммарная цена i-го ресурса, израсходованного по всем способам;
- суммарная цена всех ресурсов по всем технологическим способам.
Решим задачу на максимум продукции с ограничением по бюджету. За основу возьмем электронную модель на рис. 4.1.3. и дополним ценами ресурсов si и бюджетом В (рис. 4.1.8)
Рис. 4.1.8
Дополнительные величины:
H2:H4 – цены ресурсов (задаются);
I2:I4 – издержки (вычисляются);
I2 = G2*H2;
I3:I4 – копируется из I2;
H6 = 5000 – бюджет (задается);
I6 – издержки всего (вычисляются);
I6 = СУММ (I2:I4).
Ограничения:
B8:D8 0 – неотрицательности переменных;
I6 H6 – совокупные издержки не больше бюджета.
Будет получено решение
x1 = 0; x2 = 0; x3 = 409,84.
v = 3,08 – двойственная оценка ограничения по бюджету – увеличение бюджета на единицу увеличивает валовой продукт на 3,28.
Если ограничения по ресурсам в модели имеют смысл и не больше ( 
) и не меньше ( 
), причем все величины ( 
) не отрицательные, то в общем случае вывод о существовании или отсутствии допустимого плана сделать нельзя. Все зависит от конкретных значений величин 
и 
. Возможен случай, когда для некоторого k-го ресурса установлено такое ограничение 
, что оно не может быть выполнено из-за других ограничений. Тогда нет ни одного допустимого плана.
Заключение
Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи, которая применима к любой форме представления прямой задачи. В основу такого подхода положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к каноническому виду.
Правила получения двойственной задачи из задачи исходной.
1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.
2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.
3. В исходной ЗЛП все функциональные ограничения - неравенства вида «≤», а в задаче, двойственной ей, - неравенства вида «≥».
4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП
Список использованной литературы.
1. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.
2. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.
3. Математическое моделирование в задачах. Белолипецкий В.М., Шокин Ю.И.
4. Математическое программирование. Учебное пособие. Александра Юрьева.
5.Математическое моделирование. Учебное пособие. Коржов Е.Н
6. Основы линейного программирования. Б. Банди
7. Линейное программирование. Юдин Д.Б, Гольштейн Е.Г
Дата добавления: 2019-07-15; просмотров: 347; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!