Задача линейного программирования в том или ином виде интерпретируется как задача об оптимальном использовании ограниченных производственных ресурсов.
В первом примере приводится подробное описание технологии получения оптимального решения средствами Excel, во втором и третьем примерах раскрываются лишь основные технологические этапы.
Пример 1. Задача об оптимальном использовании ограниченных ресурсов. Предприятие имеет в своем распоряжении определенное количество производственных ресурсов: трудовые, денежные средства, сырье, оборудование, производственные площади и т.п. Допустим, например, ресурсы трех видов — трудовые, сырье и оборудование имеются в количестве соответственно 80 чел./дней, 480 кг, 130 станко-часов. Предприятие может выпускать изделия четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного изделия каждого вида (о нормах расхода производственных ресурсов), и доходах, получаемых предприятием от реализации, единицы каждого вида продукции, приведена в следующей таблице.
|
|
Ресурсы | Нормы расхода ресурсов на единицу иэдвлия | Наличие ресурсов | |||
изделие А | изделие В | изделие С | изделие D | ||
Труд | |||||
Сырье | |||||
Оборудование | |||||
Цена (тыс.руб.) |
Требуется составить такой план выпуска продукции, при котором будет получен максимальный доход от реализации продукции (сбыт всей выпущенной продукции обеспечен).
Экономико-математическая модель
Обозначим через X1, X2, X3,X4 объемы производства соответствующего вида продукции (количество изделий каждого вида).
→max
Ограничения по ресурсам:
Решение. Приведем подробное описание технологии получения решения приведенной ЗЛП.
Обозначим: М1 — один щелчок левой кнопки мыши;
М2 — двойной щелчок левой кнопки мыши.
Прежде чем приступить к решению задачи вам необходимо создать папку под своим имёнем. Порядок работы:
1. Создайте форму для ввода условий задачи. Для этого запустите Excel. Откроется чистый лист Excel. Создайте текстовую форму — таблицу для ввода условий задачи (рис.1.1).
А | B | C | D | E | F | G | H | |
Переменные | ||||||||
Х1 | Х2 | Х3 | Х4 | |||||
Значение | ЦФ | |||||||
Коэф. ЦФ | ||||||||
Ограничения | ||||||||
Вид ресурса | Левая часть | Знак | Правая часть | |||||
Труд | ||||||||
Сырье | ||||||||
Оборудование | ||||||||
Рис.1.1.
|
|
2. Укажите адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначьте через X1,X2,X3,X4 количество изделий каждого типа. В нашей задаче оптимальные значения компонент вектора Х=(X1,X2,X3,X4) будут помещены в ячейках В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. Для их производства используется два основных (определяющих) вида ресурсов S1 и S2, экономические оценки ожидаемых месячных объемов этих ресурсов составляет b1 и b2 соответственно. Например, если S1 и S2 — материальные ресурсы, то оценки b1 и b2 могут быть получены как сальдо на начало планируемого периода минус сальдо на его конец и плюс ожидаемое поступление в этом периоде согласно плану материально-технического обеспечения или согласованных предложений по финансовому плану. На предприятии имеются утвержденные в установленном порядке нормы расхода производственных ресурсов аij, i = 1, 2; j = 1, 2.
Маркетинговые исследования показали возможность сбыта любых объемов произведенной продукции по приемлемым продажным ценам — с1, и с2, соответственно (неограниченность рынка сбыта). Понятно, что в этих условиях эквивалентны два критерия оптимальности — «максимум объемов готовой продукции» и «максимум объемов реализованной продукции (выручки)».
Необходимо выбрать такой вариант месячной производственной программы, который позволил бы максимизировать выручку от продажи готовой продукции. Численные значения приведенных выше величин содержатся в таблице:
Сырье/продукция | Нормы расхода сырья, кг/ед. | Объем запасов сырья | |
Р1 | Р2 | ||
S1 | а11=1 | а11=3 | b1=300 |
S2 | а21=1 | а12=1 | b2=150 |
Цена продукции | C1=2 | C2=3 |
|
|