Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Математическая модель задачи

Практическое занятие

Аналитические методы СППР

С использованием табличного процессора Excel

Для решения задач линейного программирования в Excel имеется надстройка Поиск решения. Эта надстройка вызывается из меню Сервис. Если ее там нет, то необходимо в окне Над­стройки, появляющемся после выполнения команд Сервис ® Надстройки установить флажок Поиск решения. В том случае, когда данный флажок отсутствует, нужно переустановить Excel заново в режиме выборочной установки с указанием включения данной функции.

Рассмотрим использование данной надстройки для решения задач линейного программирования на примере решения задачи из раздела 1.3.1.

Постановка задачи

Предприятие изготавливает и реализует два вида продукции – Р₁ и Р₂. Для производства продукции используются два вида ре­сурсов – сырье и труд. Максимальные запасы этих ресурсов в сутки составляют 10 и 15 единиц соответственно. Расход ре­сурсов на изготовление каждого вида продукции, запасы и опто­вые цены продукции приведены в таблице.

Известно, что суточный спрос на продукцию Р₁ никогда не превышает спроса на продукцию Р₂ более чем на 5 ед., а спрос на продукцию Р₂ никогда не превышает 4 ед. в сутки.

Как спланировать выпуск продукции предприятия, чтобы до­ход от ее реализации был максимальным?

Математическая модель задачи

Математическая модель этой задачи имеет следующий вид. Максимизировать целевую функцию

при следующих ограничениях:

– 1-е ограничение (на сырье),

– 2-е ограничение (на труд),

– 3-е ограничение (спроса 1),

– 4-е ограничение (спроса 2),

.

Нулевые и единичные коэффициенты явно указаны в форму­лах ограничений для удобства ввода формул в Excel.

Решение задачи. Для решения этой задачи с помощью таблич­ного процессора необходимы следующие действия.

1. Создать в Excel таблицу вида:

В затененных областях необходимо будет ввести формулы для целевой функции и линейных ограничений.

Значения переменных опорного плана (Количество) для Р₁ и Р₂ могут быть заданы вручную, что позволит ускорить процесс поиска решения. Если значения опорного плана не заданы, то программа определяет их автоматически.

2. В ячейке В9 для вычисления значения целевой функции ввести формулу =СУММПРОИЗВ(В8:С8;$В$7:$С$7), которая находит сумму попарных произведений ячеек с ценами (В8:С8) на ячейки со значениями параметров ($В$7:$С$7).

Координаты ячеек с количественными значениями парамет­ров Р₁ и Р₂ преобразуются к абсолютному виду для удобства дальнейшего копирования формулы в ячейки с ограничениями. Для такого преобразования необходимо при наборе формулы после выделения нужного диапазона ячеек в таблице (В7:С7) нажать клавишу F4.

3. Для задания ограничений по ресурсу Сырье в ячейку D3 скопировать формулу из ячейки В9, заменив диапазон цен (В8:С8) на диапазон параметров расхода сырья (ВЗ:СЗ). В результате в ячей­ке ЕЗ получится формула =СУММПРОИЗВ(ВЗ:СЗ;$В$7:$С$7). Для задания остальных ограничений скопировать вновь введен­ную формулу в ячейки D4, D5 и D6.

4. После создания таблицы с исходными данными установить курсор в ячейку с формулой целевой функции (В9) и выбрать в меню Сервис функцию Поиск решения. Затем заполнить поля в появившемся окне (см. рис. 1.):

Рис. 1.

· в поле Установить целевую ячейку должен появиться адрес ячейки с формулой целевой функции (в данном случае $В$9);

· установить переключатель вида оптимизации в поле Равной: в положение максимальное (минимальное) значение; при необ­ходимости найти максимум или минимум целевой функции;

· в поле Изменяя ячейки указать диапазон ячеек со значениями параметров задачи, выделив его в таблице. В данном примере это ячейки $В$7:$С$7;

· в поле Ограничения задать вид и значения ограничений. Для этого установить курсор в поле ввода ограничений и нажать кнопку Добавить. После чего в появившемся окне Добавление ограничения (см. рис. 2) ввести в поле Ссылка на ячейку адрес ячейки с формулой соответствующего ограничения (например, D3 для ресурса сырье). Затем ввести в поле Огра­ничение предельное значение соответствующего запаса (для ресурса сырье оно находится в ячейке F3) и выбрать вид от­ношения (<, >, = и т.п.).

После нажатия кнопки Добавить (или ОК для ввода послед­него ограничения) данное ограничение попадает в список ограничений задачи.

С помощью кнопок Удалить и Изменить можно удалять вы­деленные в списке ограничения или вносить в них исправления.

Рис. 2

5. После заполнения всех полей окна нажать кнопку Параметры и в открывшемся окне Параметры поиска решения (см. рис. 3) установить флажки Линейная модель для решения задачи линей­ного профаммирования и Неотрицательные значения, если такие ограничения накладываются на все переменные задачи.

В этом окне можно так же определить параметры процесса решения: предельное время поиска решения, максимальное ко­личество итераций, точность и т.п. Флажок Показывать результа­ты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений параметров очень велик.

Рис. 3

6. Задав все параметры, нажать кнопку Выполнить для поиска решения задачи. Если решение найдено, то появляется окно с соответствующим сообщением (См. рис.4). Результаты ре­шения могут быть сохранены в файле задачи в виде сценария или добавлены в виде отдельных листов Отчет по результатам, Отчет по устойчивости и Отчет по пределам. Для сохранения результатов в виде листов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов. В этом же окне можно отказаться от полученных решений и восстановить ис­ходные значения переменных.

Рис. 4

Отчет по результатам приведен в табл. 1. В данном отче­те в графах Результат выводятся значения целевой функции и оптимального плана, а также значения исходного опорного пла­на (графа Исходное значение). Кроме того, указывается, какие ограничения являются связанными, т.е. ограничения с дефи­цитным ресурсом, а какие – нет (графа Статус), и приведены значения соответствующих дефицитов по всем ограничениям (графа Разница).

Таблица 1

Ограничения

Отчет по устойчивости выводится в следующей форме.

Таблица 2 Изменяемые ячейки

В этом отчете выводятся допустимые отклонения (графы Допустимое увеличение и Допустимое уменьшение)от заданных значений ресурсов (графа Ограничения Правая часть)и целевых коэффициентов (графа Целевой коэффициент). В этих пределах изменения ресурсов можно производить оценку изменения це­левой функции с помощью двойственных оценок (см. [7]). Сами значения двойственных оценок ресурсов приведены в графе Тене­вая цена. Пределы изменения целевых коэффициентов задают об­ласти неизменности оптимального значения целевой функции.

Большие значения пределов изменения значений, например 1Е+30 (т.е. 10³⁰) для верхней границы на спрос, означают фак­тическое отсутствие верхней границы. Это характерно для неде­фицитных ресурсов, значение которых можно увеличивать до бесконечности.

Отчет по пределам имеет вид таблицы (см. табл. 3).

Таблица 3

В этом отчете приведены значения нижних и верхних преде­лов изменения переменных оптимального плана (графы Нижний предел и Верхний предел) и для них даны соответствующие опти­мальные значения целевой функции (графы Целевой результат).