Пример решения задачи нелинейного программирования с использованием Excel

Институт математики и информатики

Кафедра прикладной информатики в управлении

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

По выполнению лабораторной работ по дисциплине

Компьютерные методы исследования систем управления

на тему: «Задачи линейного программирования

и их решение средствами Excel»

 

 

Для студентов специальности

“Прикладная информатика (в менеджменте)”

Москва

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

«Задачи линейного программирования

и их решение средствами Excel»

 

Цель – сформировать у студентов комплекс знаний необходимых для:

анализа современных проблем в области производства, торговли, финансов, денежного обращения и кредитов;

оптимальному решению тактических и стратегических задач организационного управления;

Задачи научить студентов:

владеть приемами постановки задач организационного управления;

на основе описательных задач строить математические модели;

умению выбрать соответствующий метод решения задачи;

проведению численных исследований математических моделей;

умению проведения анализа результатов вычислений;

умению выбрать наиболее эффективное управляющее решение.

Особенностью программы для студентов факультета управления является:

рассмотрение актуальных проблем организационного управления в различных структурах – производственных, торговых, финансово – кредитных;

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

Лабораторные работы призваны, на практике, помочь студентам применить знания полученные на лекциях и при самостоятельной работе. В качестве программной среды используются средства Microsoft Offis Excel (электронные таблицы MS Offis).

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

Порядок выполнения работы

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

Задание. Получить вариант задачи у преподавателя. Составить математическую модель задачи. Найти решение задачи в Excel и показать результаты поиска решения преподавателю на экране компьютера.

Отчет. Отчет по лабораторной работе представляется в тетради студента и должен содержать все полученные результаты. Отчет демонстрируется преподавателю на данном лабораторном занятии.

 

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

Тема: Задачи линейного программирования и их решение средствами Excel.

Программное обеспечение: Microsoft Excel

Пример 1. Задача оптимизации ассортимента продукции

При ограничениях на ресурсы

Компания ООО «Столы и стулья» производит два вида продукции: парты и столы. Процесс изготовления изделий происходит в цехах сборки и отделки. Данные по видам продукции приведены в таблице 1.

Таблица 1 – Словесно-арифметическая формулировка задачи в форме таблицы

Название технологического процесса	Трудоемкость технологической операции для одной парты	Трудоемкость технологической операции для одного стола	Лимит производственного времени (в часах)
Сборка	2 ч/шт	4 ч/шт
Отделка	3 ч/шт	2 ч/шт
Маржинальная прибыль на единицу продукции	25 $/шт	40 $/шт

 

Решение

Прежде чем приступить к занесению данных в электронную таблицу, необходимо выполнить промежуточный этап – на основе словесно-цифровой постановки задачи сформировать математическую (оптимизационную) модель.

Математическая модель линейной оптимизации с ограничениями формируется по следующей схеме.

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

2. Составляется оптимизируемая (целевая) функция как линейная комбинация управляемых переменных.

3. Формируются ограничения на управляемые переменные.

В данном примере в качестве управляемых переменных, в соответствии с формулированным в постановке задачи требованием, естественно выбрать количество парт (х₁) и столов (х₂).

Тогда оптимизируемая (целевая) функция Z выразит маржинальную прибыль совместной продажи (выпуска) двух товаров

Max Z = 25 x₁+40 x₂, (1)

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

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

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

В общем виде, математическая модель нелинейной задачи программирования формулируется следующим образом. Необходимо найти такой вектор n неизвестных , который доставляет максимум (или минимум) целевой функции , т.е.

и удовлетворяет системе ограничений

.

 

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

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

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

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

Пример решения задачи нелинейного программирования с использованием Excel

 

Задача. Предприятие может выпускать два вида продукции (j = 1, 2). На ее изготовление расходуется три вида ресурсов (i = 1, 2, 3). С учетом брака расход ресурсов на единицу производимой продукции j-го вида определяется выражением , а прибыль в зависимости от объемов производства равна , где – искомый объем производства продукции j-го вида; – норма расхода i-го ресурса на производство единицы продукции j-го вида; – коэффициент изменения расхода соответствующего ресурса с учетом выпуска бракованных изделий; – прибыль от реализации единицы продукции j-го вида; – коэффициент изменения прибыли, влияющий на объем производства продукции j-го вида. Требуется найти такие объемы производства продукции, при которых прибыль была бы максимальной.

 

Численные исходные данные приведены в таблице:

Ресурс	Нормы расхода ресурсов () на продукцию вида j	Запас ресурса	Коэффициент изменения норм расхода ресурсов () на продукцию вида j
				0,1	0,05
				0,2	0,2
				0,1	0,15
Прибыль за ед. продукции
Коэффициент изменения прибыли	– 0,08	– 0,1

Математическая модель

Целевая функция, которую необходимо максимизировать равна

Максимум целевой функции находится при ограничениях

Математическую модель приведем к виду, пригодному для использования в Excel. После раскрытия скобок получаем