Решение задач линейного программирования с помощью MS Excel

Пример 1

Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, наличие располагаемого ресурса, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице:

Решение:

1. Составим математическую модель, для чего введем следующие обозначения:
   x_j - количество выпускаемой продукции j-ого типа, j=1, 2, 3,4;
   b_i - количество располагаемого ресурса i -ого вида, i =1, 2, 3;
   a_ij - норма расхода i -ого ресурса для выпуска единицы продукции j-ого типа;
   c_j - прибыль, получаемая от реализации единицы продукции j-ого типа.
   Для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6х₁ единиц сырья, где х₁ - количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид: 6х₁+5х₂+4х₃+3х₄<=110.
   В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющего ресурса.
   Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:
     (7.11)
2. Создание формы для ввода условий задачи. Для данной задачи создать форму для ввода как на рис 7.7. Весь текст на этом рисунке является комментариями, и на решение задачи не повлияет.
   

   	A	B	C	D	E	F	G	H
   1		Переменные
   2	Имя	Прод1	Прод2	Прод3	Прод4
   3	Значение
   4	Нижн. гр.
   5	Верх. гр.					ЦФ	Направление
   6	Коэф. в ЦФ
   7		Ограничения
   8	Вид ресурсов					Лев. часть	Знак	Прав. часть
   9	Трудовые
   10	Сырье
   11	Финансы

   рис. 7.7
3. Ввод исходных данных. Ввести исходные данные в форму согласно условию задачи (Рис 7.8).
   

   	A	B	C	D	E	F	G	H
   1		Переменные
   2	Имя	Прод1	Прод2	Прод3	Прод4
   3	Значение
   4	Нижн. гр.	0	0	0	0
   5	Верх. гр.					ЦФ	Напр
   6	Коэф. в ЦФ	60	70	120	130	0	макс
   7		Ограничения
   8	Вид ресурсов					Лев. часть	Знак	Прав. часть
   9	Трудовые	1	1	1	1	0	<=	16
   10	Сырье	6	5	4	3	0	<=	110
   11	Финансы	4	6	10	13	0	<=	100

   Рис 7.8
4. Ввод зависимостей из математической модели. Ввести зависимости из математической модели (7.11). В режиме представления формул это будет выглядеть как на рис 7.9
   

   	A	B	C	D	E	F	G	H
   1		Переменные
   2	Имя	Прод1	Прод2	Прод3	Прод4
   3	Значение
   4	Нижн. гр.	0	0	0	0
   5	Верх. гр.					ЦФ	Напр
   6	Коэф. в ЦФ	60	70	120	130	=СУММПРОИЗВ(B$3:E$3;B6:E6)	макс
   7
   8	Вид ресурсов	Ограничения				Лев. часть	Знак	Прав. часть
   9	Трудовые	1	1	1	1	=СУММПРОИЗВ(B$3:E$3;B9:E9)	<=	16
   10	Сырье	6	5	4	3	=СУММПРОИЗВ(B$3:E$3;B10:E10)	<=	110
   11	Финансы	4	6	10	13	=СУММПРОИЗВ(B$3:E$3;B11:E11)	<=	100

   Рис 7.9
5. Назначение целевой функции, ввод ограничений и граничных условий. Вызвать диалоговое окно Поиск Решения: Сервис-Поиск решения… (рис 7.10)
     Рис 7.10
   Назначить целевую функцию: $F$6
   Ввести адреса искомых переменных: $B$3:$E$3
   Ввести ограничения, нажав кнопку Добавить. Появиться диалоговое окно Добавление ограничения (рис 7.11)
   

     Рис 7.11
   Ввести граничные условия: $B$3:$E$3>=$B$4:$E$4
   Ввести ограничения: $F$9:$F$11<=$H$9:$H$11
6. Решение задачи
   После ввода данных вызвать диалоговое окно Параметры… (рис 7.12)
     Рис 7.12
   Параметры, используемые по умолчанию, подходят для решения большинства задач. В нашем случае необходимо только установить флажок Линейная модель, что обеспечивает применение симплекс-метода. ОК.
   На экране вновь появится диалоговое окно Поиск решения. Выполнить.
   На экране появится диалоговое окно Результаты поиска решения. Решение найдено и результат оптимального решения задачи приведены в таблице (Рис. 7.14).
     Рис 7.13
   
   

   	A	B	C	D	E	F	G	H
   1		Переменные
   2	Имя	Прод1	Прод2	Прод3	Прод4
   3	Значение	10	0	6	0
   4	Нижн. гр.
   5	Верх. гр.					ЦФ	Направление
   6	Коэф. в ЦФ	60	70	120	130	1320	макс
   7
   8	Вид ресурсов	Ограничения				Лев. часть	Знак	Прав. часть
   9	Трудовые	1	1	1	1	16	<=	16
   10	Сырье	6	5	4	3	84	<=	110
   11	Финансы	4	6	10	13	100	<=	100

   Рис 7.14
   Из рис. 7.14 видно, что в оптимальном решении Прод1=10, Прод2=0, Прод3=6, Прод4=0. При этом максимальная прибыль будет составлять 1320, а количество использованных ресурсов: трудовых=16, сырья=84, финансов=100.
7. Важным фактором, помогающим принять решение является графическое представление полученного результата.
     Рис 7.15
8. Преодоление несовместности и анализ оптимального решения оставляем на самостоятельное изучение. Этот материал можно найти в [5].

Пример 2

Компания производит два основных типа товара (Изделие-1, Изделие-2). Изделие-1 требует 2 единицы сырья А и 2 ед. сырья В, оно приносит прибыль компании 2 денежные единицы. Изделие-2 требует 3 ед. сырья А и 5 ед. сырья В, оно приносит прибыль 4 д. е. Найдите оптимальный план производства, если доступно всего 1200 единиц сырья А и 1600 единиц сырья В.

Решение:

Пусть Х - количество производимого товара первого изделия, Y - количество производимого товара второго изделия. Составим математическую модель.

Создадим форму для ввода условий задачи и введем исходные данные: