КП_Тишинский. 5. Решение задачи линейного программирования вручную 10

• Название: 5. Решение задачи линейного программирования вручную 10
• Анкор: КП_Тишинский.doc
• Дата: 11.04.2018
• Размер: 5.67 Mb.
• Имя файла: КП_Тишинский.doc
• Тип: Решение; #17925
• страница: 6 из 6

Реализация модели задачи на компьютере

1. Реализация модели задачи линейного программирования в MS Excel

Мощным средством анализа данных Excel является надстройка Solver (Поиск решения). С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.
Программа Поиск решений (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных та нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:

• 
  количество неизвестных (decision variable) – 200;
  
• 
  количество формульных ограничений (explicit constraint) на неизвестные – 100;
  
• 
  количество предельных условий (simple constraint) на неизвестные – 400.
  

Разработчик программы Solver компания Frontline System уже давно специализируется на разработке мощных и удобных способов оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).
Высокая эффективность их применения объясняется интеграциею программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора  MS Excel встроенная в его среду программа  Solver есть  наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса.
По умолчанию в Excel надстройка Поиск решения отключена. Чтобы активизировать ее в Excel 2007, щелкните значок Кнопка Microsoft Office , щелкните Параметры Excel, а затем выберите категорию Надстройки. В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти. В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

В Excel 2003 и ниже выберите команду Сервис/Надстройки, в появившемся диалоговом окне Надстройки установите флажок Поиск решения и щелкните на кнопке ОК. Если вслед за этим на экране появится диалоговое окно с предложением подтвердить ваши намерения, щелкните на кнопке Да. (Возможно, вам понадобится установочный компакт-диск Office).



Рисунок 6 15 Активация надстройки «Поиск решения»
Процедура поиска решения

1. 
   Создаём таблицу с формулами, которые устанавливают связи между ячейками.
   
2. 
   
   
   

Рисунок 6 16 Таблица в режиме чисел


Рисунок 6 17 Таблица в режиме формул
Здесь:

С2,D2-результат (количество килограммов корма 1-го типа, и корма 2-го типа);

С3,D3-коэффициенты целевой функции;

E3-значение целевой функции;

С3-D6-коэффициенты ограничений;

G4-Е6-вычисляемые значения левой части ограничений

3. 
   Выделяем целевую ячейку, которая должна принять необходимое значение, и выберите команду: Tools > Solver (Сервис > Поиск решения). Поле Set Target Cell (Установить целевую ячейку) открывшегося диалогового окна надстройки Solver (Поиск решения) будет содержать адрес целевой ячейки.
   
4. 
   Устанавливаем переключатели Equal To (Равной), задающие значение целевой ячейки, — Мах (максимальному значению), Min (минимальному значению) или Value of (значению). В последнем случае вводим значение в поле справа.
   
5. 
   Указываем в поле By Changing Cells (Изменяя ячейки), в каких ячейках программа должна изменять значения в поисках оптимального результата.
   
6. 
   Создаём ограничения в списке Subject to the Constraints (Ограничения). Для этого щелкните на кнопке Add (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение.
   
7. 
   Щелкаем на кнопке на кнопке Options (Параметры), и в появившемся окне установливаем переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям)
   

Рисунок 6 18 диалоговое окно «Поиск решения»

8. 
   Щелкнув на кнопке Solver (Выполнить), запускаем процесс поиска решения.
   Когда появится диалоговое окно Solver Results (Результаты поиска решения), выбераем переключатель Keep Solve Solution (Сохранить найденное решение) или Restore Original Values (Восстановить исходные значения).
   
9. 
   Щелкаем на кнопке ОК.
   

Рисунок 6 19 диалоговое окно «Результаты поиска решения»

10. 
    Получаем результирующие данные где:
    

E3 – значение целевой функции;

C2 – колличесво килограммов корма 1-го вида необходимое для нормы рациона;

D2 – колличесво килограммов корма 2-го вида необходимое для нормы рациона;

H4 – показатели превышения нормы потребления белка;

H5 – показатели превышения нормы потребления углеводов;

H6 – показатели превышения нормы потребления протеина.



Рисунок 6 20 Результаты решения в виде таблицы
Ответ: Оптимальная стоимость дневного рациона с соблюдением норм потребления питательных веществ составляет 31.6 ден. ед. при приобретении 1.6 кг. корма 1-го вида, и 4.2 кг. корма 2-го вида. При соблюдение данного рациона животное дополнительно получит 18.8 единиц протеина.

1. Реализация модели задачи линейного программирования в MathCAD

Система MathCAD позволяет упростить решения задач линейного программирования, используя при этом основные функции Maximize и Minimize.

1. 
   Рассмотрим порядок выполнения решения задачи линейного программирования в системе MathCAD с системой ограничений двух или трех переменных.
   
2. 
   Введем целевую функцию;
   
3. 
   Введем некоторые начальные значения переменных. В линейных задачах эти значения безразличны, в нелинейных могут быть весьма критичны
   

x:=0

y:=0;

4. 
   Сформулируем блок данных. Для этого введем слово GIVEN, щелкнем ниже и введем ограничения - неравенства;
   
5. 
   Введем задание на минимизацию, набрав p:=minimize(f,x,y);
   
6. 
   Обозначение P выбрано произвольно, оно будет восприниматься системой как массив, элементам которого по окончании работы программы будут присвоены значения переменных x, и y, найденные в ходе решения задачи минимизации
   
7. 
   Сформулируем запрос к системе о результатах решения задачи. Для этого введем с клавиатуры P=;
   
8. 
   Наберем ;
   

Рисунок 6 21 Решение задачи в программе MathCAD
Получаем результат в виде, со значениями x=1.6, а y=4.2

Ответ: 1.6 килограмм корма 1-го вида и 4.2 килограмм корма 2-го вида обеспечат минимальные затраты в размере 31.6 денежных единиц и восполнят дневной рацион содержащий минимальный набор питательных веществ.

2. Анализ полученных результатов

Решая прямую задачу линейного программирования графическим методом, симплекс - методом, в программе MS Ехсеl с помощью «Поиска решений», в программе MathCAD получены одинаковые результаты:

Оптимальный состав дневного рациона содержащего необходимый набор питательных веществ соблюдается при использовании, 1.6 кг корма 1-го вида и 4.2 кг корма 2-го вида При этом минимальные затраты составляют 31.6 ден. ед..