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

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

 

     

2. Пример  СЛАУ

 

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

 

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

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

     

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

     

     x₁ ³ 0;

     x₂ ³ 0;

     x₃ ³ 0.

3. Описание  решения данной задачи

 

     Решим поставленную выше задачу с применением  EXCEL.

 

     

3. Исходные  данные

     Содержание  ячеек:

     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 – плановый расход ресурсов меньше их запаса.

     

4. Поиск решения

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

 

     

5. Результат решения

 

     Основные  результаты видны в таблице (рис. 5). По сравнению с условиями задачи, показанными на рис. 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 готовит три отчета: Результаты, Устойчивость, Пределы.

6. Отчет по результатам 

     1-я  таблица – целевая ячейка –  дает значение целевой функции,  которая уже имеется в таблице  EXCEL, значит, эти данные избыточны.

     2-я  таблица – изменяемые ячейки – дает значение переменных, которые уже имеются в таблице EXCEL, эти данные тоже избыточны.

     3-я  таблица – ограничения – дает  оценку ограничений. Колонка «значение»  дает значения планового расхода  ресурсов и переменных – эти  данные имеются в таблице EXCEL и здесь избыточны. Столбец «статус» значением «связанное» отмечает ограничения (не больше или не меньше), которые в результате решения превратились в строгие равенства, прочие ограничения имеют статус «несвязанные». Столбец «разница» показывает, на какую величину ограничения отклонились от строгого равенства. Так, например, ограничение 1-го ресурса 500, плановое значение 271,6, разница = 500 – 271,6 = 228,4.

 

7. Отчет по устойчивости

     Отчет по устойчивости изображен на рис. 7 Он состоит из двух таблиц.

     Таблица «изменяемые ячейки» показывает значения переменных, которые уже  имеются в таблице EXCEL. Столбец «нормируемый градиент» показывает, как влияет увеличение переменных на единицу на величину целевой функции. Таблица «ограничения» содержит важную информацию в столбце «Лагранжа множители». Эти величины в литературе имеют различные названия: объективно обусловленные оценки (О.О.О.) по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем – двойственные оценки и обозначать – v_i, где i – номер ограничения. В данном примере v₁ = 0, v₂ = 20,0, v₃ = 4,4. Отчет по пределам показан на рис. 8.

 
 

8. Отчет по пределам

     В этом отчете уже в третий раз дается значение целевой функции 15880, в пятый раз значение переменных (х₁ = 86, х₂ = 0, х₃ = 268). Нижний предел для всех переменных = 0, так, установлены ограничения по переменным. Верхний предел равен соответственно 86, 0 и 268, так устанавливают ограничения по ресурсам. Целевой результат показывает значение целевой функции при соответствующих значениях переменных. Если х₁ = 0, то ЦФ = 10720 и т.д.

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

 

     

 

     Пусть:

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

 

      .

 

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

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

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

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

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

     Решим задачу на максимум продукции с ограничением по бюджету. За основу возьмем электронную  модель на рис. 3 и дополним ценами ресурсов s_i и бюджетом В (рис. 9)

 

     

9. Исходные  данные с ценами на ресурсы и бюджет

     Дополнительные  данные:

     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. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.
2. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.
3. Математическое моделирование в задачах. Белолипецкий В.М., Шокин Ю.И.
4. Математическое Белолипецкий В.М.