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

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

Пример 3.3. Найдем решение задачи из примера 3.1. Формальная постановка выглядит следующим образом:

найти

при ограничениях

h: х₁ + х₂ = 400,

х₁ ≥ 0, х₂ ≥ 0.

Решение. Шаблон решения задачи приведен на рис.3.1:

Рис. 3.1. Шаблон решения задачи 3.1 с исходными данными.

Пояснения к рис. 3.1:

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

Причем х₀₁ = 1, х₀₂ = 1.

Ячейки синего цвета содержат исходные данные:

• в стоке 2 это значения переменных х₀₁ = 1и х₀₂ = 1;

• в строках 4 (B4:G4) и 6 (B6:G6) - это коэффициенты целевой функции f и ограничения h соответственно (пустые ячейки интерпретируются как нули);

Ячейки желтого цвета C2 и F2 отведены под искомые переменные.

В ячейках бежевого цвета размещены расчетные формулы:

Адрес ячейки	Формула
D2	=C2^2
G2	=F2^2
I4	=СУММПРОИЗВ(B2:G2;B4:G4)
I6	=СУММПРОИЗВ(B2:G2;B6:G6)

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

Рис. 3.2. Исходные данные для запуска процедуры численного решения задачи.

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

В ячейках C2 и F2 мы видим оптимальные значения переменных

которые совпадают со значениями, найденные в примере 3.1 методом множителей Лагранжа.

В ячейке I4 число 214 412 означает минимальные общие издержки производства, соответствующие найденной оптимальной структуре выпуска продукции.

Пример 3.4. Найдем решение задачи из примера 3.2. Формальная постановка выглядит следующим образом:

Найти

При ограничениях

Решение. Шаблон решения задачи приведен на рис.3.3:

Рис. 3.3. Шаблон решения задачи 3.2 с исходными данными.

Пояснения к рис. 3.3:

Принципиально структура шаблона не меняется. Ввиду того, что в целевой функции отсутствуют свободные члены, исключены соответствующие переменные х₀₁ и х₀₂. В ячейках В6, В7 размещены свободные члены ограничений

Ячейки желтого цвета C2 и D2 отведены под искомые переменные c начальными значениями х₁ = 1 и х₂ = 1. Такие начальные значения выбраны с целью простоты проверки правильности вычислений. Поскольку задача имеет один экстремум, то выбор начальной точки на результат решения не влияет. Если в качестве исходной взять точку х₁ = 10 и х₂ = 10 (кстати, лежащую за пределами области допустимых решений), то результат решения не изменится.

В ячейках шаблона размещены следующие расчетные формулы:

Адрес ячейки	Формула
E2	=C1*D1
F2	=C2^2
G2	=D2^2
I4	=СУММПРОИЗВ(C2:G2;C4:G4)
I6	=СУММПРОИЗВ(C2:D2;C6:D6)+B6
I7	=СУММПРОИЗВ(C2:D2;C7:D7)+B7

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

Рис. 3.4. Исходные данные для запуска процедуры численного решения задачи.

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

В ячейках C2 и D2 мы видим оптимальные значения переменных

которые совпадают со значениями, найденные в примере 3.2 c использование условий Куна – Таккера. Значения ячеек I6,I7 показывают, что ограничения h₁ и h₂ выполняются, что свидетельствует о принадлежности оптимального решения области допустимых решений. В ячейке I4 число 80 означает максимальное значение целевой функции.

Контрольные задания по теме 3

Предприятие располагает двумя способами производства данного вида продукции. В течение рассматриваемого периода времени необходимый объем продукции равен В = Х₁ + Х₂, где Х₁ и Х₂ - объемы производства по соответствующему технологическому способу. Затраты производства S при каждом способе зависят от объемов нелинейно:

И(Х₁) = с₀ + с₁ Х₁ + с₂Х₁² , с_0, с_1, с₂ > 0,

И(Х₂) = р₀ + р₁ Х₂ + р₂Х₂² , р_0, р_1, р₂ > 0.

Необходимо объем производства так распределить между технологическими способами, чтобы минимизировать общие затраты производства.

Числовые данные для решения задач 1-10 представлены в таблице. Решить задачу двумя способами: методом множителей Лагранжа и с помощью надстройки Поиск решения Excel:

Номер задачи	р0	р1	р2	с0	с1	с2	В

Задание по теме 4: Методы управления запасами.

Методические указания по теме 4

Основные понятия

Решение проблемы рассматривается на интервале в один год. На примере одного склада с однономенклатурным запасом. Спрос на изделия постоянный. Пополнение запасов может осуществляться либо периодически (циклическая модель), либо при снижении запаса до некоторого уровня (уровневая модель).

Объем заказа – количество заказываемых изделий (размер партии товара).

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

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

Штраф за дефицит – это убытки, понесенные из-за неудовлетворенного спроса.

За хранение единицы изделия берется плата C_h. D – годовой спрос на изделия. Стоимость подачи заказа C₀ – это транзакционные издержки по реализации заказа (не зависят от объема заказа). Основная цель построения системы управления запасами – минимизация суммарных издержек.