Решение задач линейного программирования

 

Решение задачи линейного программирования в среде EXCEL осуществляется в соответствии со следующим алгоритмом

1. Ввод условий задачи

1.1.  Создание формы для ввода условий задачи. Форма для ввода условий задачи

….

…,

имеет следующий вид

 

 

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

2. Ввод зависимостей из математической модели. Заполняются ячейки содержащие: функцию, реализующую целевую функцию задачи, функции реализующие левые части ограничений задачи.

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

2.1.1. Поместить курсор в ячейку, отведенную под значение целевой функции.

2.1.2. Выбрать кнопку Мастер функций.

2.1.3.
Выбрать в окне Категория категорию математические

2.1.4. Выбрать функцию СУММПРОИЗВ.

2.1.5. Заполнить диалоговое окно функции СУММПРОИЗВ.

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

3.2.   Ввод зависимостей для левых частей ограничений.

3.2.1. Поместить курсор в ячейку, отведенную под левую часть ограничения.

3.2.2. Выбрать кнопку Мастер функций.

3.2.3. Выбрать в окне Категория категорию математические.

2.1.6. Выбрать функцию СУММПРОИЗВ.

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

2.1.8. Копировать содержимое ячейки в буфер

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

4. Ввод основных параметров модели в диалоговом окне Поиск решения.

4.3.  Войти в меню Сервис и выбрать пункт Поиск решения.

4.4.
 Заполнить параметры диалогового окна Поиск решения.

4.4.1. В пункте Установить целевую указать ячейку, отведенную под целевую функцию.

4.4.2. В соответствии с решаемой задачей выбрать направление целевой функции.

4.4.3. Нажать кнопку Добавить. Появится диалоговое окно для построения ограничений задачи.В левой части указывается ячейка (группа ячеек), в которой содержится левая часть ограничения, в центре - знак ограничения, в правой части - ячейка (группа ячеек) с правой частью ограничения. После ввода каждого ограничения нужно нажимать на кнопку Добавить. Когда все ограничения задачи построены, нужно нажать на кнопку Отмена и вернуться в диалоговое окно Поиск решения.

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

 

 С помощью команд, находящихся в этом диалоговом окне, можно вводить условия для решения задач оптимизации всех классов. В ряде пунктов данного окна записаны значения, используемые по умолчанию. Команды, используемые по умолчанию, подходят для большей части практических задач. Команда Максимальное время служит для назначения времени в секундах, выделяемого на поиск решения задачи. В это поле можно ввести значение, не превышающее 32767 с (более 9 часов). Значение 100, используемое по умолчанию, подходит для решения большинства задач. Команда Предельное число итераций служит для назначения числа итераций…

4.4.5. Установить флажок Линейная модель. Это обеспечит применение симплекс – метода.

4.4.6. Нажать на кнопку Выполнить. Начнется решение составленной математической модели задачи. Через какое-то время появится диалоговое окно Результаты поиска решения.

 

 

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

В качестве примера рассмотрим решение следующей задачи производственного планирования

Пример 1. Предприятие выпускает три вида продукции: Прод1, Прод2, Прод3, Прод4. Требуется определить, в каком количестве надо выпускать эти продукты, чтобы получить максимальную прибыль. Известно, что для изготовления данных продуктов требуются ресурсы трех видов: трудовые, сырьевые, финансы. Нормы расхода (количество ресурса каждого вида, необходимое для выпуска единицы продукции каждого типа), а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в следующей таблице.

 

 

ресурс	Прод1	Прод2	Прод3	Прод4
Трудовые	60	70	120	130
Сырье	1	1	1	1
Финансы	6	5	4	3
Прибыль	4	6	10	13

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

1. Составим форму для данной задачи линейного программирования

2. Введем зависимости из математической модели

3. Вызовем диалоговое окно Поиск решения. В нем устанавливается целевая ячейка (F7), изменяемые ячейки (B3:E3), указывается направление поиска (максимизация). Далее выбирается команда Добавить и в появившемся диалоговом окне Добавление ограничения вводятся ограничения: F10<=H10, F11<=H11, F12<=H12.

Условия неотрицательности переменных можно ввести в диалоговом окне Параметры поиска решения. В окне Параметры поиска решения устанавливается также флажок Линейная модель.

4.
Запустим программу на выполнение из окна поиск решения. На экране появится диалоговое окно Результаты поиска решения. В данном диалоговом окне сделан вывод о том, что найдено оптимальное решение.

 

Результат решения задачи приведен в таблице

Данная таблица показывает, что максимальная прибыль (F7=1320) будет достигнута предприятием при следующем выпуске продукции: прод1=B4=10, прод2=C4=0, прод3=D4=6, прод2=E4=0. В специально отведенных ячейках таблицы отражается количество использованных ресурсов: трудовых=F10=16, сырья=F11=84, финансов=F12=100. 

5. Представим результаты решения задачи графически.

Проведем анализ полученного решения. Анализ решения осуществляется на основании трех видов отчетов, представленных в окне Результаты поиска решения: результаты, устойчивость, пределы. Начнем с Отчета по результатам. Данный отчет находится на отдельном листе. Отчет состоит из трех таблиц. Таблица 1 приводит сведения о целевой функции. В столбце Исходно приведены значения целевой функции до начала вычислений – 0,а в столбце Результат – значение целевой функции в оптимальном решении - 1320. Таблица 2 приводит значения искомых переменных, полученные в результате решения задачи. Таблица 3 показывает результаты оптимального решения для ограничений задачи: трудовые, сырье, финансы. В столбце Формула приведены ограничения в том виде, в котором они были введены в диалоговом окне Поиск решения, в столбце Значение приведены величины использованного ресурса.

 Трудовые ресурсы использованы в количестве 16, сырье – 84, финансы – 100. В графе Разница показано количество неиспользованного ресурса. Трудовые ресурсы использованы полностью, остаток сырья составляет 26, финансы использованы полностью. Если ресурс используется полностью, то в столбце Состояние указывается связанное; при неполном использовании ресурса в этом столбце указывается несвязанное.

    Второй тип отчета – Отчет по устойчивости. Данный отчет находится на отдельном листе и состоит из двух таблиц.

В столбце Результирующее значение таблицы 1 приводится описанный ранее результат решения задачи. Столбец Нормированная стоимость показывает, что при принудительном включении единицы прод1 в оптимальное решение целевая функция не изменится, прод2 – уменьшится на 10, прод3 – не изменится, прод4 – уменьшится на 20. Столбцы Допустимое увеличение и Допустимое уменьшение показывают, что если прибыль от реализации прод1 будет изменяться в пределах от 60-40 до 60+12, то оптимальное решение задачи не изменится, аналогично для прод2 – от 70-10 до 70+(1Е+30), прод3 – от 120-30 до 120+13,33333333, прод4 – 130-20 до 130+(1Е+30).

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

Теневая цена позволяет определить максимальную цену, по которой стоит покупать дополнительные единицы ресурсов. Столбцы Допустимое увеличение и Допустимое уменьшение показывают, что изменение трудовых ресурсов в пределах от 16-3,545454 до 16+6 не приводит к изменению оптимального набора выпускаемых продуктов, аналогично для сырья – от 110-(1Е+30) до 110+26, для финансов – от 100-60 до 100+36.

Третий тип отчета – Отчет по пределам. Данный отчет состоит из одной таблицы.

 

	Целевое
Ячейка	Имя	значение
$F$7	коэф.в ЦФ	1320
	Изменяемое		Нижний	Целевой	Верхний	Целевой
Ячейка	Имя	значение	предел	результат	предел	результат
$B$4	значение прод1	10	0	720	10	1320
$C$4	значение прод2	0	0	1320	0	1320
$D$4	значение прод3	6	0	600	6	1320
$E$4	значение прод4	0	0	1320	0	1320

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