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

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

ПОИCК РЕШЕНИЙ в среде     EXCEL

 

Поиск решения – это надстройка EXCEL, позволяющая реализовывать модели линейной, нелинейной и дискретной оптимизации. Если в меню Данные отсутствует команда Поиск решения, значит необходимо загрузить эту надстройку.

 

Решение оптимизационной задачи состоит  из нескольких этапов:

 

Этап 1.

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

 

Этап 2.

Подготовить таблицу данных в EXCEL (рис 1).

• На листе Excel обозначить имеющиеся переменные : В1:Е1;
• Зарезервировать ячейки для их значений – изменяемые ячейки В2:Е2: эти ячейки пока оставим пустыми, по окончании решения в этих ячейках будут находится оптимальные значения управляющих переменных;
• Ввести в отдельные ячейки В5:Е5 коэффициенты целевой функции ;
• Обозначить целевую функцию : в ячейку F5 (целевая ячейка) ввести формулу для вычисления значения этой функции со ссылкой на ячейки значений коэффициентов В5:Е5 и переменных В2:Е2.
• Для каждого из ограничений задачи заполнить ячейки с исходными данными: в ячейки В8:Е10 ввести коэффициенты левых частей неравенств ; в ячейки Н8:Н10 ввести правые части ограничений ; в ячейках G8:G10 указать знак неравенства (<=, >= или =);
• В ячейки F8:F10 ввести формулы для вычисления значений левых частей ограничений .

Рис. 1.

Для ввода формул , удобно использовать мастер функций: / математические / СУММПРОИЗВ.

 

Этап 3.

Для запуска Поиск решения выбрать команды Данные Поиск решения. После выбора команды Поиск решения появиться диалоговое окно Поиск решения (рис 2.). В нем есть три основных поля:

• Установить целевую ячейку;
• Изменяя ячейки;
• Ограничения;

Установить  целевую ячейку – указывается ячейка, в которой находится формула для вычисления значения функции цели - F5.  Эта ячейка связана с другими ячейками с помощью формул. Здесь же выбирается направление оптимизации: наибольшее или наименьшее значение функции цели  ищется в задаче.

Рис. 2.

 

Изменяя ячейки - указываются зарезервированные изменяемые ячейки В2:Е2, соответствующие управляющим переменным в модели, значения в которых будут изменяться для достижения экстремума  целевой функции. В этих ячейках в результате расчета будут находиться значения переменных оптимального плана  .  Для поиска решения можно указать до 200 изменяемых ячеек.

К этим ячейкам предъявляются два  основных требования: они не должны содержать формул и должны влиять на значение целевой ячейки, т.е. их адреса должны  использоваться в формуле, введенной в целевую ячейку.

Ограничения модели определяются с помощью значений соответствующих ячеек (рис 3). Структура ограничения, введенного в Поиске решения, полностью соответствует ограничению, построенному в модели: левая часть, знак, правая часть:

ссылка на ячейку – указываются ячейки, в которых введены формулы для вычисления левых частей неравенств системы ограничений F8:F10 (не путать с ячейками, содержащими коэффициенты левых частей ограничений В8:Е10). Ограничения могут налагаться как на целевую ячейку, так и на переменные (до 100 дополнительных  ограничений);

тип каждого из ограничений модели ( ) задается (вводится) в специальном окне диалога при выполнении команды;

ограничение - указываются ячейки, в которых введены правые части выражений в системе ограничений Н8:Н10.

Рис3.

 

В режиме Параметры (Рис. 4) окна диалога Поиск решения задается тип модели (линейная или нелинейная) и прямые ограничения ( отмечаются галочками поля «Линейная модель» и «Неотрицательные значения»).

   Рис. 4

 

Этап 4.

После команды Выполнить осуществляется поиск оптимального решения и в итоге появляется диалоговое окно Результат поиска решения (Рис. 5).

Рис. 5

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

Необходимо проконтролировать успешное завершение решения задачи: появляется сообщение Решение найдено. Все ограничения и условия оптимальности выполнены.

 

 

Задача 1.

Найти оптимальный план, обеспечивающий максимум функции цели

при заданных ограничениях:  

                                                     

Решение.

Этап 1. Выполнен - модель задана.

Этап 2.

1. Подготовим форму для ввода условий задачи (рис 6).

Зарезервированы ячейки:

В3:С3 – для оптимальных значений управляющих переменных ,

D5- для оптимального значения целевой функции.

 

2. Введем исходные данные в созданную форму (рис.7.)

 

Рис. 6. Форма  для ввода данных.

Рис 7. Данные введены.

 

3. Введем зависимость для целевой функции
• Курсор в ячейку D5. (Обозначим через - один щелчок левой кнопкой мыши).
• Курсор на кнопку Мастер функций. .
• На экране диалоговое окно Мастер функций шаг 1 из 2.

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

• В окне Функции выбрать СУММПРОИЗВ.
• Готово . На экране появиться диалоговое окно СУММПРОИЗВ, показанное на рис. 8.

 

Рис 8. Ввод формулы для вычисления целевой функции.

 

• Курсор в поле  Массив 1 : ввести В3:С3. Во все диалоговые окна адреса удобно вводить не с клавиатуры, а протягиванием мыши (не отпуская левой кнопки) по ячейкам, адреса которых следует указать в этом поле. Чтобы на адресах установить знак $ нажмите на клавиатуре кнопку .  В результате в поле  Массив 1 будут указаны адреса $В$3:$С$3.
• Курсор в поле  Массив 2 : ввести В4:С4.

• Готово На экране: в ячейку D5 введена формула вычисления целевой функции (Рис. 9.)

Рис. 9. Ввод формулы в ячейку целевой  функции.

 

4. Введем зависимости, стоящие в левых частях ограничений. Это можно сделать так же, как и для целевой функции через Мастер функций:

• Курсор в ячейку D9.
• Курсор на кнопку Мастер функции / Математические / СУММПРОИЗВ.
• В поле  Массив 1 ввести В3:С3. Чтобы на адресах установить знак $ нажмите на клавиатуре кнопку .  В результате в поле  Массив 1 будут указаны адреса $В$3:$С$3.
• В поле  Массив 2 ввести В9:С9.
• Готово

В пустой ячейке D9 появляется посчитанное значение 0 (ячейки В3:С3 пустые - значения переменных равны 0).

В ячейку D10 формулу можно ввести аналогично, или скопировать формулу из ячейки D9. На этом ввод зависимостей закончен (Рис. 10).

 

После копирования  формул обязательно проверьте адреса!

 

Замечание: так как во всех зависимостях надо ссылаться на изменяемые ячейки В3:С3, для них использованы абсолютные адреса.

 

Рис. 10. Ввод зависимостей.

 

Этап 3. Запуск Поиск решений

После выбора команд  Поиск решения появится диалоговое окно Поиск решения (Рис. 11)

• Назначение целевой ячейки: курсор в поле Установить целевую ячейку.  . Курсор в ячейку  D5. .
• Ввести направление целевой функции: максимальному значению.
• Ввести адреса искомых переменных: курсор в поле  Изменяя ячейки. . Выделить мышью ячейки В3:C3.

Рис. 11. Подготовка Поиска решения.

 

• Ввести ограничения:
• курсор в поле Ограничения .  Выбрать режим Добавить . Появляется диалоговое окно Добавление ограничений, как показано на  рис. 12.

 

Рис. 12. Ввод ограничений.

 

• курсор в поле  Ссылка на ячейку
• выбрать мышью ячейки D9:D10

          !!! Обратите  внимание: указываются адреса ячеек,  содержащих формулу.

• ввести знак ограничения <=
• курсор в правое окно Ограничение .
• указать мышью адреса F9:F10
• если ввод ограничений закончен, выберете , если

надо ввести другие ограничения, то Добавить.

 

В результате этих действий экран  будет выглядеть, как представлено на рис 13.

   

Рис 13. Введены все условия для решения задачи.

 

• Выбрать параметры модели: рис 4.            

            

Этап 4. Выполнить.

На экране диалоговое окно  Результат поиска решения.(рис. 14.)

 

 

Рис. 14. Решение найдено.

 

В результате решения получен ответ: максимальное значение целевой функции составит 1810,5 при значениях переменных и .

 

 

Задача 2.   Решение транспортной задачи в среде EXCEL

 

На трех станциях отправления имеется  соответственно 30, 50, и 20 ед. однородного  груза, который нужно доставить  в четыре пункта назначения согласно их потребностям. Эти данные, а также стоимость перевозки единицы груза от каждой станции отправления к каждому пункту назначения указаны в таблице. Составить план перевозок грузов, чтобы затраты на эти перевозки были минимальными.

Пункты отправления	Запасы груза	Пункты назначения
	30	1	8	2	3
	50	4	7	5	1
	20	5	3	4	4
Потребности		15	35	40	30

Решение.

Этап 1.

Часто условие транспортной задачи оформляют матрицей:

1	8	2	3	30
4	7	5	1	50
5	3	4	4	20
15	35	40	30

 

Построим математическую модель транспортной задачи.

1. «Составить план перевозок грузов» - значит определить сколько, от куда и куда надо перевезти груза, чтобы достичь поставленной цели - «затраты на эти перевозки были минимальными». Введем управляющие переменные: - количество груза, перевозимого из пункта в пункт ( ).

2. Стоимость этой перевозки составит . Тогда целевая функция  - суммарные затраты, связанные с реализацией всего плана перевозок – запишется выражением: