Мат_моделир_2015_заоч_ЭП_ФИН / Оптим_план / Оптим_план

Задача №1

Оптимизация плана выпуска продукции

Задача оптимизации плана выпуска продукции относится к задачам линейного программирования(ЛП). Ее решение возможно как графическим способом ( для 2 или 3 переменных), так и средствами MS EXCEL. Рассмотрим постановку задачи ЛП и составление математической модели на простейшем примере.

Пример 2.1. Предприятию требуется составить оптимальный по реализации суточный производственный план выпуска двух видов деталей при определенных возможностях четырех типов станков. В таблице 2.1 приведены типы станков, их ресурсы, время, затрачиваемое на обработку одной детали каждого вида конкретным типом станка и прибыль от реализации одной детали каждого вида.

Таблица 1.1.Сводка исходных данных

Типы станков	Деталь № 1	Деталь № 2	Ресурсы станков в сутки (часы)
Токарный Фрезерный Сверлильный Долбежный	1 0,5 1 0	1 1 0 1	18 12 12 9
Прибыль от одной детали, грн.	400	600

1. Решение

Обозначим , - количество деталей каждого вида.

1. Составление математической модели

Ограничения на ресурсы станков:

Граничные условия: .

Дополнительные ограничения: , - целые.

Запишем целевую функцию, определяющую суммарную прибыль предприятия.

 max.

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

2. Графический способ решения задачи ЛП

Определим множество допустимых решений, т.е. множество точек, координаты которых удовлетворяют системе ограничений и граничным условиям. Неравенства означают, что множество допустимых планов расположено в пересечении положительных полуплоскостей (рис.2.1).

Рассмотрим первое ограничение (ресурс «токарный станок»), переписав его в виде равенства

Строим прямую линию по двум точкам. Пусть = 0, тогда = 18. Если = 0, то = 18. Геометрический смысл неравенства – полуплоскость, все точки которой удовлетворяют этому неравенству. Для определения полуплоскости расположения точек допустимого плана, нужно в неравенство подставить координаты произвольной точки рассматриваемой полуплоскости, например, точки с координатами =0 и = 0 (начало координат). Так как неравенство удовлетворяется (0  18), то допустимые решения (точки) будут расположены в полуплоскости ниже прямой, характеризующей ресурс «токарный станок». Отметим расположение определяемых точек штриховкой прямой «токарный станок». Остальные ограничения изобразим графически аналогично.

Рис. 1.1 Графическое решение задачи

По рис. 2.1 видно, что если будет выполняться ограничение по фрезерному станку, то ограничение по токарному станку несущественно и его можно отбросить. Существенны ограничения в виде многоугольника ОАВСД, т.е. этот многоугольник определяет множество допустимых планов, но какое из сочетаний и дает предприятию максимальную прибыль?

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

Определяем оптимальный план. Для этого строим линию уровня по уравнению целевой функции

= ,

где а – произвольное число. Пусть а = 1200, т.к. 1200 делится без остатка на 400 и 600.

При смещении линии уровня параллельно самой себе в направлении возрастания переменных и значение целевой функции растет и самое большое ее значение будет в точке С. В этой точке линия уровня еще касается множества допустимых решений.

Все точки на линии уровня определяют одну и ту же прибыль.

На рис.1.1 точка С имеет координаты = 12 и = 6. Определим координаты точки С по формулам. В этой точке пересекаются две прямые линии, характеризующие существенные ограничения,

0,5 + = 12;

= 12 .

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

3. Решение задачи в MS EXCEL

Технология работы в среде ЭТ при решении задач оптимизации с помощью надстройки «Поиск решения»

Задачи линейного, нелинейного и целочисленного программирования очень эффективно решать с помощью надстройки «Поиск решения» приложения Excel. Рассмотрим технологию работы при решении задачи примера 2.1.

1. Загрузите программу Excel 2000.

2. Размещение информации на рабочем листе ЭТ приведено на рисунке 2.2.

Рис. 1.2

Введите исходную информацию:

• коэффициенты при неизвестных (управляемых переменных) в ограничениях в диапазон ячеек В6:С9;

• коэффициенты при неизвестных целевой функции в диапазон ячеек В10:С10;

Выделите ячейки для результатов решения задачи:

• неизвестные значения управляемых переменных (результаты решения) будут получены в ячейках В5:С5 (выделены двойной рамкой); первоначально значения управляемых переменных равны нулю;

• значения правых частей ограничений рассчитываются в диапазоне ячеек Е6:Е9;

• ячейку В12 для значения целевой функции.

3. Ввести формулы, по которым считаются ограничения и целевая функция, в соответствующие ячейки результатов решения (Рис.1.2). Формулы эти представляют собой суммы произведений, поэтому для их задания можно использовать функцию СУММПРОИЗВ мастера функций.

4. Установите курсор на ячейку В12, в которую будет записано после оптимизации значение целевой функции, войдите в меню Сервис и выберите надстройку Поиск решения. В диалоговом окне Поиск решения (рис. 2.3):

• в поле Установить целевую функцию должен быть адрес В12;

• установите переключатель Равной в положение максимальному значению;

• в поле Изменяя ячейки ввести диапазон ячеек В5:С5.

Рис. 1.3. Диалоговое окно надстройки «Поиск решения»

5. Задайте ограничения:

• щелкнуть на кнопке Добавить диалогового окна Поиск решения;

• заполним диалоговое окно Добавление ограничений (рис.2.4)

Рис.1.4 Диалоговое окно «Добавление ограничений»

• аналогично введите остальные ограничения.

• добавьте ограничения, указывающие на целочисленность определяемых переменных, путем установки переключателя  в положение цел:

В5 цел целое, С5 цел целое;

• после ввода всех ограничений щелкнуть на кнопке ОК.

6. Щ елкнуть на кнопке Параметры диалогового окна Поиск решения. В диалоговом окне Параметры (рис. 2.5) установить флажки в поле линейная модель и неотрицательные значения. Щелкнуть на кнопке ОК.

Рис. 1.5. Диалоговое окно «Параметры поиска решения»

7. Щ елкнуть на кнопке Выполнить диалогового окна Поиск решения. После окончания расчета появится диалоговое окно Результаты поиска решения (рис. 2.6).

Рис. 1.6. Диалоговое окно «Результаты поиска решения»

8. Щелкнуть на кнопке ОК. Результаты решения появятся в ячейках В5:С5 и В12 (Рис.2.7).

Рис. 1.7

4. Выводы

Таким образом, решение задачи оптимизации дает не только оптимальный план 12 деталей №1 и 6 деталей №2, прибыль в размере 8400 грн., но и информацию о загрузке оборудования, на основе которой можно планировать последовательность приобретения оборудования, если предусматривается увеличение объема выпускаемой продукции. В данном случае недогружен долбежный станок , а остальные полностью исчерпали временной ресурс. Для увеличения плана выпуска можно увеличить плановый ресурс станков в сутки, если это возможно по технологическим и организационным данным.

Приведенный пример носит условный характер, но в нем отражены основные принципы построения, реализации и анализа моделей оптимизации производственных программ предприятий.

5