 |
Описание решения данной задачи
|
|
|
|
Решим поставленную выше задачу с применением 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 – номер ограничения. В данном примере v 1 = 0, v 2 = 20,0, v 3 = 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 – совокупные издержки не больше бюджета.
Будет получено решение
x 1 = 0; x 2 = 0; x 3 = 409,84.
v = 3,08 – двойственная оценка ограничения по бюджету – увеличение бюджета на единицу увеличивает валовой продукт на 3,28.
Если ограничения по ресурсам в модели имеют смысл и не больше ( 
) и не меньше ( 
), причем все величины ( 
) не отрицательные, то в общем случае вывод о существовании или отсутствии допустимого плана сделать нельзя. Все зависит от конкретных значений величин 
и 
. Возможен случай, когда для некоторого k -го ресурса установлено такое ограничение 
, что оно не может быть выполнено из-за других ограничений. Тогда нет ни одного допустимого плана.
Заключение
В результате проделанной работы был рассмотрен теоретический материал, посвященный решению двойственных задач линейного программирования, и процесс их решения был автоматизирован, с помощью программы MS Excel.
|
|
|
Результатом работы над курсовым проектом является программа для решения задач линейного программирования с помощью двойственного симплекс-метода.
Список используемой литературы
1. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.
2. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.
3. Математическое моделирование в задачах. Белолипецкий В.М., Шокин Ю.И.
4. Математическое Белолипецкий В.М.
|
|
|
