Лабораторная работа № 5

Тема: задачи линейного программирования.

Цель: приобрести навыки экономико-математического моделирования и ознакомить с решением задач линейного программирования в среде EXEL.

Теоретические сведения:

К детерминированным моделям принятия решений относятся оптимизационные модели, которые в первую очередь нашли широкое применение в экономике, поскольку связаны с планированием целенаправленной деятельности при существующих ограничениях на ресурсы. Несмотря на смысловое разнообразие таких задач, все они формально сводятся к одной общей постановке: найти значения переменных x₁ ,x₂ ,..., x_n , доставляющие максимум (минимум) заданной скалярной функции f ( x₁ ,x₂ ,...,x_n ) при условиях g _i ( x₁ ,x₂ ,...,x_n )[≤ , = , ≥] b_i (i = 1,m),которые образуют систему ограничений.

 

 

Данная задача является задачей математического программирования, а функция f (x₁ ,x₂ ,..., x_n ) называется целевой функцией. Обычно вид функций f и g_i (i = 1,…, m)известен,константы b_i заданы,величины m, n являются целыми числами (в отдельных случаях между ними устанавливается соотношение m<n). Специально оговариваются ограничения, выраженные в требованиях неотрицательности и целочисленности x_j (j = 1,…, n).

В основу классификации задач математического программирования положены особенности функций f и g_i, встречающихся в конкретных исследованиях. Различают два основных класса задач – задачи линейного и нелинейного программирования. К первым относятся те, в которых и целевая функция f , и все функции g_i (i = 1,.. m)линейны относительно переменных x_j ( j = 1,n),ко вторым–те,в которых присутствуют различного рода нелинейности.

 

Общая форма задачи линейного программирования имеет вид

 

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

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

 

Компьютерная поддержка решения задач линейного программирования осуществляется в среде EXEL с помощью надстройки Поиск решения. Для этого необходимо осуществить следующую последовательность действий.

 

1. Ввод исходных данных (коэффициенты целевой функции и ограничений, нижние и верхние границы переменных).

 

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

2.1. Ввод зависимости для целевой функции: поместить курсор в соответствующую значению целевой функции ячейку и выбрать команду Вставка ⇒ Функция.На экране появится диалоговое окно Мастер Функций,показанное на рис.1.

 

Рис. 1.

 

В разделе Категория представлен список 11 категорий функций. При выборе одной из категорий в списке Функция появляется перечень функций, включенных в эту категорию. Для функции цели выберем категорию математические,функцию СУММПРОИЗ.Появится Палитра формул Excel, которая используется для определения аргументов функции, как показано на рис. 2. В массивы 1 и 2 заносятся диапазоны ячеек, содержащих значения переменных и коэффициенты функции цели.

 

 

Рис. 2.

 

2.2. Ввод зависимостей для левых частей ограничений осуществляется так же, как для целевой функции. При этом в массивы 1 и 2 заносятся диапазоны ячеек, содержащих значения переменных и коэффициенты ограничения.

 

2.3. Ввод остальных параметров модели. Необходимо выбрать команду Сервис ⇒ Поиск решения. На экране появится диалоговое окно Поиск решения,как показано на рис. 3.

 

 

Рис.3.

 

В поле Установить целевую ячейку укажите адрес ячейки, отведенной под значение целевой функции, или щелкните в рабочем листе на этой ячейке. В зависимости от цели задачи – максимизировать или минимизировать значение в этой ячейке – установите переключатель Равной максимальному значению или Равной минимальному значению.Затем определите изменяемые ячейки, указав их диапазон или выделив их на рабочем листе.

Далее ограничения добавляются по одному и отображаются в окне Ограничения.Для добавления ограничений щелкните на кнопке Добавить.Появится диалоговое окно Добавление ограничения, как на рис. 4.

11

 

Рис. 4.

 

В это диалоговое окно нужно ввести ссылку на ячейку, в которой содержится левая часть ограничения, оператор ограничения из раскрывающегося списка операторов и ссылку на ячейку, в которой содержится правая часть ограничения. Для добавления очередного ограничения щелкните на кнопке Добавить.После ввода последнего ограничения щелкните на кнопке ОК. Вывернетесь к диалоговому окну Поиск решения. Щелкнув на кнопке Параметры,вызовите диалоговое окно Параметры поиска решения,изображенное нарис. 5.

 

 

Рис. 5.

 

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

• Максимальное время.Предоставляет возможность ограничить максимальное время (в секундах) решения задачи. Если появится сообщение о том, что время на решение истекло, можно добавить время для поиска решения.

 

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

 

• Допустимое отклонение.Максимальное отклонение в процентах дляцелочисленных решений (имеет смысл, только если задано целочисленное ограничение).

 

• Линейная модель.Может ускорить поиск решения,но только при условии, если все зависимости в модели линейны.

 

• Показывать результаты итераций.Если эта опция активизирована, то после выполнения очередной операции поиск решения приостанавливается, и на экране будут отображены найденные результаты.

 

• Автоматическое масштабирование.Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине.

• Разделы Оценка, Разности и Метод поиска. Эти опции позволяют контролировать некоторые технические аспекты решения задачи.

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

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

 

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

3. Теперь для выполнения процедуры поиска решения введены все исходные данные. Чтобы начать процесс решения задачи, щелкните на кнопке Выполнить в диалоговом окне Поиск решения.В строке состояния будет отображаться ход решения задачи. Через некоторое время на экране появится диалоговое окно Результаты поиска решения, показанное на рис. 6.

 

Рис. 6.

 

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

 

Пример.Фирма производит пять видов офисной мебели,для которыхиспользует шесть видов материала в различных количествах (рис. 7). Например, для выпуска модели 2 необходимы: 1 ед. пластика, 1 ед. клея, 1 ед. древесины, 5 ед. краски, 2 ед. упаковочной бумаги и не требуется металлическая фурнитура.

 

Рис. 7.

 

Текущие запасы каждого вида материала представлены в столбце Н. В строке 11 показана прибыль от производства одной единицы каждой модели офисной мебели. Количество произведенных моделей каждого вида представлено в диапазоне В12 : F12. Эти значения будут определяться с помощью процедуры поиска решения. Значение общей прибыли находится в ячейке В13. Требуется определить оптимальный план выпуска мебели, максимизирующий прибыль. В качестве ограничения выступает требование использовать для выпуска продукции только имеющееся в наличие количество ресурсов. На рис. 8 показаны результаты, полученные с использованием EXEL. Проанализируем их на основании отчетов трех типов.

 

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

 

Отчет по устойчивости (рис. 10). В первой таблице отчета в столбце Результирующее значение представлен результат решения задачи.

 

 

 

Рис. 8.

 

 

 

Рис. 9.

 

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

 

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

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

 

Рис. 10.

 

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

 

 

Рис. 11.