Двойственность задачи в линейном программировании

Запишем конкретный числовой пример

 

Рис. 

 

2.2 Построение математической  модели

 

Теперь приступим к  созданию математической модели, т.е. к  математической записи задачи.

Целевая функция:

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

x₁ ³ 0;

x₂ ³ 0;

x₃ ³ 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. Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:

B8:D8 0 – неотрицательности переменных;

G2:G4 F2:F4 – плановый расход ресурсов меньше их запаса.

Теперь электронная  модель сформирована и можно решать задачу. Для этого нужно вернуться  в окно «поиск решения» и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Результаты, Устойчивость, Пределы.

 

Рис. 4.1.4

 

Основные результаты видны в таблице (рис. 4.1.4.). По сравнению с условиями задачи, показанными на рис. 4.1.3., появились данные:

1. Значение целевой  функции в ячейке G6 = 15880;

2. Значения переменных  в ячейках B8:D8: х₁ = 86, х₂ = 0, х₃ = 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. Столбец «нормируемый градиент» показывает, как влияет увеличение переменных на единицу на величину целевой функции. Таблица «ограничения» содержит важную информацию в столбце «Лагранжа множители». Эти величины в литературе имеют различные названия: объективно обусловленные оценки (О.О.О.) по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем – двойственные оценки и обозначать – v_i, где i – номер ограничения. В данном примере v₁ = 0, v₂ = 20,0, v₃ = 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, в пятый раз значение переменных (х₁ = 86, х₂ = 0, х₃ = 268). Нижний предел для всех переменных = 0, так, установлены ограничения по переменным. Верхний предел равен соответственно 86, 0 и 268, так устанавливают ограничения по ресурсам. Целевой результат показывает значение целевой функции при соответствующих значениях переменных. Если х₁ = 0, то ЦФ = 10720 и т.д.

Запишем математическую модель рассмотренной задачи в общем  виде:

 

 

Пусть:

В-бюджет, т.е. количество денег, которое можно израсходовать на приобретение ресурсов для производства продукции, а s_i – рыночная цена i-го ресурса. Тогда единственное ограничение по ресурсам будет выглядеть следующим образом:

 

.

 

Смысл этого ограничения - нельзя израсходовать ресурсов на сумму больше, чем В.

Здесь:  - расход i-го ресурса в натуральном выражении по j-му технологическому способу;

- расход i-го ресурса в натуральном выражении по всем способам;

- суммарная цена i-го ресурса, израсходованного по всем способам;

- суммарная цена всех ресурсов по всем технологическим способам.

Решим задачу на максимум продукции с ограничением по бюджету. За основу возьмем электронную модель на рис. 4.1.3. и дополним ценами ресурсов s_i и бюджетом В (рис. 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 – совокупные издержки не больше бюджета.

Будет получено решение

x₁ = 0; x₂ = 0; x₃ = 409,84.

v = 3,08 – двойственная оценка ограничения по бюджету – увеличение бюджета на единицу увеличивает валовой продукт на 3,28.

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

 

Заключение

 

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

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

Целью работы является описание и усвоение того, что, в общем, представляет двойственные задачи в линейном программировании (ДЗ в ЛП)

Для достижения поставленной цели были поставлены следующие задачи:

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

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

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

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

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

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

 

 

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

1. Аттеков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации: Учеб. Для вузов/ Под ред. В.С. Зарубина, А.П. Крищенко. – 2-е изд., стереотип. М.: Изд-во МГТУ им. Н.Э. Баумана, 2003
2. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учебное пособие. – М.: Финансы и статистика, 2003
3. Берюхова Т.Н.Банк производственных задач в расчетах на ЭВМ: учебное пособие. – Тюмень.: ТюмИИ, 2002. – 124с.
4. Вентцель Е.С. Исследование операций: задачи, принципы, методология.- 2-е издание, стереотип. – М.: Наука,2001
5. Воротницкий Ю.И. «Исследование операций».
6. Давыдов Э.Г. «Исследование операций», 1990 г..
7. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000 г..
8. Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. – М.: Физматлит, 2001. – 264с.
9. Коротков М., Гаврилов М. «Основы линейного программирования», 2003 г..
10. Кузнецов А.В. Математическое программирование: учебное пособие для вузов. – М.: Высшая школа, 2001. – 352с.
11. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 2002 г.
12. Лищенко «Линейное и нелинейное программирование», М. 2003 г..
13. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004 г..
14. Мочалов И.А. Нечеткое линейное программирование. // Промышленные АСУ и контроллеры. – 2006. - № 10. – с.26-29.
15. Пашутин С.Оптимизация издержек и технология формирования оптимального ассортимента. // Управление персоналом. – 2005. - №5. – с.20-24.
16. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 2001 г.
17. Теха Х. «Введение в исследование операций», Издательский дом «Вильямс», 2001 г..
18. Филькин Г.В., «Линейное программирование» (лекции), Шахты, 2007 г..
19. Чупрынов Б.П., Красс М.С. Основы математики и ее приложения в экономическом образовании: Учебник. – 2-е издание , испр. – М.: Дело, 2003
20. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учебное пособие. – 3-е издание. – М.: Дело, 2004