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

>     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 

     Изменяемые  Ячейки

 

     Ограничения

     Рис. 4.1.5 

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

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

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

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

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

     Изменяемые  ячейки

 

     Ограничения

     Рис. 4.1.6 

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

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

 

     Рис. 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-го ресурса установлено такое ограничение , что оно не может быть выполнено из-за других ограничений. Тогда нет ни одного допустимого плана.

 

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

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