Оптимизация задач линейного, целочисленного и нелинейного програм-мирования

КДЗ

Задание:

Оптимизация задач линейного, целочисленного и нелинейного програм-мирования

С использованием Excel.

 

                 Оптимизация задач линейного,  целочисленного и нелинейного  программирования.

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

Сервис Надстройки Поиск решений (отметить) Ок.

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1.1. Активация команды Поиск решения

Поиск решения при оптимизации линейного программирования использует симплекс- метод.

В программе  Excel в меню Сервис применяя команду Поиск решения, откроется диалоговое окно где устанавливается адрес целевой ячейка, диапазон переменных.

Рис. 1.2. Диалоговое окно надстройки Поиск решения

С помощью  кнопки Добавить вводятся необходимые ограничения.

Рис. 1.3. Диалоговое окно надстройки

Кнопка Параметры открывает диалоговое окно Параметры поиска решения, где по умолчанию стоит определенный набор команд.

Рис. 1.4. Диалоговое окно надстройки, уточняющее параметры поиска решения

По умолчанию  значение допустимого отклонения стоит 5%. Это значит, что процедура оптимизации  продолжается только до тех пор, пока значение целевой функции будет  отличаться от оптимального не более  чем на 5%. Более высокие значения допустимого отклонения ускоряют работу средства Поиск решения при оптимизации моделей, однако существует риск, что найденное значение будет значительно отличаться от истинного оптимума соответствующей задачи. Устанавливая значение допустимого отклонения, например, равным 0 %, мы заставляем Поиск решения находить истинный оптимум задачи за счет, возможно, более длительного времени решения.

Для улучшения  работы средства Поиска решения настройка диалогового окна Параметры поиска решения часто применяется при решении задач нелинейного программирования.

Значение  в поле Сходимость используется для завершения процесса поиска решения, когда изменение целевой функции происходит очень медленно. Если установить меньшее значение сходимости, чем предусмотрено по умолчанию (0,0001), программа продолжит процесс оптимизации даже при малых изменениях целевой функции.

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

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

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

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

Команда Выполнить запускает решение задачи. Поиск решения просит уточнить: сохранить ли найденное решение или нет.

Рис. 1.5.  Диалоговое  окно надстройки

Рекомендации по поиску решения задач.

1. При задании в диалоговом окне Поиска решения правых частей ограничений всегда следует указывать ссылки на ячейки в табличной модели. Ячейки в правых частях неравенств в табличной модели должны содержать константы, а не формулы. Пример решения задач И В EXCEL

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

Постановка задачи. 
Предприятие производит продукцию n (5) видов при этом используя сырье m (3) типов. Расход каждого типа сырья на производство изделий представлен таблицей:                                                                    Таблица 2.1.

Производство  обеспечено сырьем каждого типа в  количестве (4300) с. (3460) у.е. и (4460) с.  Рыночная цена единицы составляет (10) с. (14) с. (12) с (16) с.

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

Экономико-математическая модель.

Исходя  из условия, делается вывод о том, что эта задача является задачей  линейного программирования.  Обозначим  за неизвестные переменные (i =1….5) объем производства соответствующих изделий. Значения таблицы 3.1. представляют собой матрицу с коэффициентами ( ). Где i – номер строки, j – номер столбца (например, ).

В общем  виде  система ограничений имеет  вид:

С учетом значений задачи получаем.

Дополнительные  ограничения:

, , , , .

Необходимо  найти оптимальный план выпуска  продукций (т.е. ), который обеспечит максимальную выручку. Пусть f – выручка от реализации продукций. Тогда

В общем  виде целевая функция примет вид:

,

где   – рыночные цены соответствующих изделий (i =1….5);

– объем производства соответствующих  изделий.  

Исходя  из условий задачи:

Для некоторых  производственных задач целесообразно  найти оптимальный план производства, содержащий целые значения. Поэтому  в дополнительные ограничения следует  добавить: (i =1….5).

Табличная модель.

Модель  производственной задачи состоит из трех таблиц: таблицы ограничений  и расхода сырья, таблицы плана  выпуска (искомых переменных), таблицы  прибыли. До оптимизации ячейки переменных [В11:В15] заполняются произвольным набором значений (не противоречащим ограничениям). Таким образом, задается первое приближение. Кроме того это необходимо, чтобы увидеть расчет всех ячеек, заполненных формулами.

 

Рис. 2.1. Табличное представление модели

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

Массив Расход сырья [G5:G7] рассчитывается путем умножения матрицы Вид сырья на матрицу План выпуска. Для этого необходимо выделить ячейки расход сырья, применить функцию МУМНОЖ, выделить перемножаемые массивы и одновременно нажать три клавиши: Shift, Ctrl, Enter.

Матрица Остаток рассчитывается, как [Запас сырья]−[Расход сырья]. Ячейка Е11 содержит значение целевой функции, рассчитанной как сумма произведений значений цены на план выпуска соответствующего вида продукции.

Более наглядно заполнение ячеек табличной формы  задачи представлено на рисунке 2.2.

Рис. 2.2. Табличная модель с представленными формулами

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

Рис. 2.3. Диалоговое окно надстройки Поиск решения

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

Замечаем, что оптимум значительно больше предыдущего значения целевой функции. Разность составляет: 7500- 5200=2300                                          

 

 Вывод: 
Оптимальный план производства, при данных условиях, состоит в том, что продукцию 1-ого и 4-ого видов необходимо производить в объеме 750 и 650 c. соответственно, а продукции 2- ого – 4- ого видов не выпускать в производство. При этом обеспечивается максимальная выручка в размере 2300c.

ЛИТЕРАТУРА

1. Тюрин Ю.Н., Макаров А.А. Статистически  анализ данных на компьютере. М., 1997.

2. Дюк В.А. Обработка данных на ПК в примерах. СПб, 1997.

3. Кулаичев А.П. Методы  и средства анализа данных. М., 1998