Лабораторная работа №1. Задачи линейного программирования

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

В первом примере приводится подробное описание технологии получения оптимального решения средствами Excel, во втором и третьем примерах раскрываются лишь основные технологические этапы.

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

Ресурсы	Нормы расхода ресурсов на единицу иэдвлия	Наличие ресурсов
изделие А	изделие В	изделие С	изделие D
Труд
Сырье
Оборудование
Цена (тыс.руб.)

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

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

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

→max

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

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

Обозначим: М1 — один щелчок левой кнопки мыши;

М2 — двойной щелчок левой кнопки мыши.

Прежде чем приступить к решению задачи вам необходимо создать папку под своим имёнем. Порядок работы:

1. Создайте форму для ввода условий задачи. Для этого запустите Excel. Откроется чистый лист Excel. Создайте текстовую форму — таблицу для ввода условий задачи (рис.1.1).

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

Рис.1.1.

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

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

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

Рис.1.2.

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

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

· курсор на кнопку «Мастер функций», расположенную на панели инструментов;

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

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

· М1;

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

· М1. Кнопка «ОК». На экране появляется диалоговое окно СУММПРОИЗВ;

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

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

· кнопка «ОК». На экране: в ячейку F4 введена функция.

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

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

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

· на панели инструментов кнопка Копировать в буфер → М1;

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

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

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

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

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

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

Примечание. Содержимое ячеек F7—F9 необходимо проверить. Они обязательно должны содержать правильные формулы.

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

Рис. 1.3

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

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

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

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

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

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

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

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

Рис. 1.4

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

· выберите знак ограничения ≤

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

· указатель мыши на кнопку Добавить → М1. На экране вновь диалоговое окно Добавление ограничений;

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

· после введения последнего ограничения нажмите кнопку ОК.

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

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

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

Рис. 1.5

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

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

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

Через непродолжительное время появится диалоговое окно Результаты поиска решения, в котором можно указать тип отчета т.д., и исходная таблица с заполненными ячейками В3:Е3 для значений Х_i и ячейка F4 с максимальным значением целевой функции.

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

Пример 1.2. На некоторый временной период, например месяц, осуществляется формирование производственной программы выпуска двух видов изделий Р1 и Р2. Для их производства используется два основных (определяющих) вида ресурсов S₁ и S₂, экономические оценки ожидаемых месячных объемов этих ресурсов составляет b₁ и b₂ соответственно. Например, если S₁ и S₂ — материальные ресурсы, то оценки b₁ и b₂ могут быть получены как сальдо на начало планируемого периода минус сальдо на его конец и плюс ожидаемое поступление в этом периоде согласно плану материально-технического обеспечения или согласованных предложений по финансовому плану. На предприятии имеются утвержденные в установленном порядке нормы расхода производственных ресурсов а_ij, i = 1, 2; j = 1, 2.

Маркетинговые исследования показали возможность сбыта любых объемов произведенной продукции по приемлемым продажным ценам — с₁, и с₂, соответственно (неограниченность рынка сбыта). Понятно, что в этих условиях эквивалентны два критерия оптимальности — «максимум объемов готовой продукции» и «максимум объемов реализованной продукции (выручки)».

Необходимо выбрать такой вариант месячной производственной программы, который позволил бы максимизировать выручку от продажи готовой продукции. Численные значения приведенных выше величин содержатся в таблице:

Сырье/продукция	Нормы расхода сырья, кг/ед.	Объем запасов сырья
	Р1	Р2
S1	а11=1	а11=3	b1=300
S2	а21=1	а12=1	b2=150
Цена продукции	C1=2	C2=3