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

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

Пример 3. Задача об оптимальном использовании ограниченных ресурсов. Предприятие имеет в своем распоряжении определенное количество производственных ресурсов: трудовые, денежные средства, сырье, оборудование, производственные площади и т.п. Допустим, например, ресурсы трех видов – трудовые, сырье и оборудование имеются в количестве, соответственно, 80 чел.-дней, 480 кг, 130 станко-часов. Предприятие может выпускать изделия четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного изделия каждого вида (о нормах расхода производственных ресурсов), и доходах, получаемых предприятием от реализации, единицы каждого вида продукции, приведена в таблице 7.

Таблица 7

Данные условия задачи

Ресурсы	Нормы расхода ресурсов на единицу иэдвлия				Наличие ресурсов
	изделие А	изделие В	изделие С	изделие D
Труд	7	2	2	6	80
Сырье	5	8	4	3	480
Оборудование	2	4	1	8	130
Цена (тыс. руб.)	3	4	3	1

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

Экономико-математическая модель

Обозначим через x₁, х₂, х₃,, х₄ объемы производства соответствующего вида продукции (количество изделий каждого типа).

1. Ограничения по ресурсам:

трудовые ресурсы, чел.-дней:

7х₁ + 2х₂ + 2хз + 6х₄ ≤ 80;

сырьё, кг:

5x₁+8х₂ + 4х_з + 3х₄ ≤ 480;

оборудование, станко-часов:

2х₁+4х₂+х₃+8х₄ ≤ 130.

2. Условие неотрицательности – х₁, х₂, х₃, х₄ ≥ 0.

3. Целевая функция – это математическая запись критерия оптимальности, т.е. выражение, которое необходимо максимизировать.

Z(x) = 3x₁ + 4х₂ + 3х₃ + х₄→max.

Решение. Приведем подробное описание технологии получения решения приведенной ЗЛП.

1. Создать форму для ввода условий задачи. Запустите Excel, выбрав Microsoft Excel из подменю Программы главного меню Windows. Открывается чистый лист Excel. Создайте текстовую форму – таблицу для ввода условий задачи (рис. 14).

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

Рис. 14. Таблица для ввода условий задачи

2. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначьте через X₁, Х₂, Х₃, Х₄ количество изделий каждого типа. В нашей задаче оптимальные значения компонент вектора X = (X₁, Х₂, Х₃, Х₄) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции – в ячейке F4.

3. Ввести исходные данные задачи в созданную форму – таблицу, представленную на рисунке 15. Сохраните таблицу, так как она должна быть представлена в отчете по лабораторной работе.

	А	B	C	D	E	F	G	H
1			Переменные
2		Х1	Х2	Х3	Х4
3	Значение					ЦФ
4	Коэф. ЦФ	3	4	3	1
5			Ограничения
6	Вид ресурса					Левая часть	Знак	Правая часть
7	Труд	7	2	2	6		<=	80
8	Сырье	5	8	4	3		<=	480
9	Оборудование	2	4	1	8		<=	130
10

Рис. 15. Порядок сохранения таблицы

В строке Меню указатель мыши – на имя Файл. В развернутом меню – команда Сохранить как. Появляется диалоговое окно Сохранение документа. Путем перебора папок в строке Папка должна быть установлена папка с фамилией студента. Далее курсор переведите в строку Имя файла и присвойте ему имя. Далее нажать кнопку Сохранить.

4. Ввести зависимость для целевой функции:

• курсор в ячейку F4;

• курсор на кнопку Мастер функций, расположенную на панели инструментов.

На экране появляется диалоговое окно Мастер функций шаг 1 из 2 (рис. 16).

Рис. 16. Окно «Мастер функций»

• курсор в окно Категория на категорию Математические;

• курсор в окно Функции на СУММПРОИЗВ;

• на экране появляется диалоговое окно СУММПРОИЗВ (рис. 17);

• в строку Массив 1 ввести В$3:Е$3;

• в строку Массив 2 ввести В4:Е4;

• кнопка ОК».

Рис. 17. Окно функции СУММПРОИЗВ

Примечание. Адреса ячеек во вес диалоговые окна удобно вводить не с клавиатуры, а протаскивая мышь по ячейкам, чьи адреса следует ввести.

5. Ввести зависимости для ограничений:

• курсор в ячейку F4;

• на панели инструментов кнопка Копировать в буфер;

• курсор в ячейку F7;

• на панели инструментов кнопка Вставить из буфера;

• курсор в ячейку F8;

• на панели инструментов кнопка Вставить из буфера;

• курсор в ячейку F9;

• на панели инструментов кнопка Вставить из буфера.

Примечание. Содержимое ячеек F7:F9 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рисунке 18 (в качестве примера представлено содержимое ячейки F7).

Рис. 18. Содержание ячеек F7:F9

В строке Меню указатель мыши – на имя Сервис. В развернутом меню команда Поиск решения. Появляется диалоговое окно Поиск решения (рис. 19).

Рис. 19. Диалоговое окно «Поиск решения»

6. Назначить целевую функцию (установить целевую ячейку):

• курсор в строку Установить целевую ячейку;

• введите адрес ячейки $F$4;

• введите направление целевой функции в зависимости от условия вашей задачи – Максимальному значению или Минимальному значению);

• курсор в строку Изменяя ячейки;

• введите адреса искомых переменных В$3:Е$3.

7. Ввести ограничения:

• указатель мыши на кнопку Добавить. Появляется диалоговое окно Добавление ограничения (рис. 20);

Рис. 20. Диалоговое окно Добавление ограничения

• в строке Ссылка на ячейку введите адрес $F$7;

• введите знак ограничения <=;

• в строке Ограничение введите адрес $Н$7;

• указатель мыши – на кнопку Добавить. На экране вновь диалоговое окно Добавление ограничения (рис. 20).

• введите остальные ограничения задачи, по вышеописанному алгоритму;

• после введения последнего ограничения кнопка ОК.

На экране появляется диалоговое окно Поиск решения с введенными условиями (рис. 21).

Рис. 21. Окно Поиск решения

8. Ввести параметры для решения ЗЛП:

• в диалоговом окне указатель мыши на кнопку Параметры. На экране появляется диалоговое окно Параметры поиска решения (рис. 22);

Рис. 22. Окно Параметры поиска решения

• установите флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения;

• указатель мыши на кнопку ОК. На экране диалоговое окно Поиск решения;

• указатель мыши на кнопку Выполнить.

Через непродолжительное время появится диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками ВЗ:ЕЗ для значений X_j и ячейка F4 с максимальным значением целевой функции (рис. 23).

Рис. 23. Окно Результаты поиска решения

Полученное решение означает, что максимальный доход – 150 тыс. руб. – предприятие может получить при выпуске и реализации 30 изделий вида В и 10 изделий вида С. При этом трудовые ресурсы и фонд рабочего времени оборудования будут использованы полностью, а из 480 кг ресурса сырья будет использовано 280 кг (рис. 24).

Рис. 24. Результаты решения в исходной таблице