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

Рассмотрим  простой пример.

Минимизировать 

F(X1, X2) = -4X1-6X2+X12+3X22

при условиях

X1 + 2 X2 £ 4,

X1, X2 ³ 0.

Ставим задачу минимизации до нуля функции 

g(X1, X2, l, Y, V1, V2) = X1V1 + X2V2 + lY

при условиях (8), где 

 

Ищем начальный  опорный план, методом искусственного базиса (не обращая внимания на коэффициенты, меньшие M):

 

Находим начальный  опорный план исходной задачи

X1 = X2 = V1 = 0, V2 = 2, Y = 4, l = 4,

для которого g(W) = 0´0 + 0´2 + 4´4 = 16 > 0

Отыскиваем  градиент grad g(W) = {0, 2, 4, 4, 0, 0} и берем его компоненты в качестве коэффициентов "линейной формы" (нормали к поверхности, определяемой функцией g(W), в выбранной точке).

 

Получен оптимальный  план X = (2, 1).

Заметим, что  при ограничениях AX = B , X ³ 0 исчезнет переменная Y, снимутся условия неотрицательности на l и потребуется минимизировать XTV при условиях:

2 D X + ATl - V = -C

AX = B

X, V ³ 0.

При других отклонениях  постановки задачи от выбранного здесь  стандарта можно элементарными  приемами прийти к нему (вместо максимизации F(X) искать минимум F(X), условие AX ³B заменить на B - AX£0 и т.п.).

 

1.2.5. Дробно-линейное  программирование

Пусть стоит  задача максимизации дробно-линейной функции

 

при линейных ограничениях

 

Предположим, что знаменатель в (1) положителен  при всех X, удовлетворяющих (2)-(3).

Если обозначить

 

 

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

 

при условиях

 

 

Рассмотрим  в качестве примера задачу максимизации

 

при условиях

 

С учетом (4) получаем задачу максимизации

- 3R + 2Z1 + 4Z2 - 5Z3

при условиях 5R + 3Z1 - Z2 = 1

Z1 - Z2 ³ 0

-15 R + 5 Z1 + 3 Z2 + 10 Z3 £ 0

R > 0, Z1, Z2, Z3 ³ 0.

 

Отсюда Z1 = Z2 = 3/14, Z3 = 0, R = 4/35 и соответственно Xopt = (15/8, 15/8, 0), max Q(X) = 33/35.

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

 

Глава II. Решение  задачи нелинейного программирования средствами электронных таблиц

2.1. Постановка  задачи

Предприятие выпускает электронные изделия  двух типов 

(изделия  A и B). На выпуск изделий расходуется  платина и палладий. На одно  изделие A требуется 13 г платины  и 8 г палладия, на одно изделие  B - 6 г платины и 11 г палладия. Предприятие имеет возможность  использовать не более 90 г платины  и не более 88 г палладия.

Изделия A продаются  по цене 12 тыс. ден.ед., изделия B – по 10 тыс. ден.ед. Величины себестоимости изделий (т.е. затраты на их выпуск) зависят от объема их производства и приближенно описываются следующими формулами:

• себестоимость  одного изделия A: 7+0,2X1, где X1 - объем  производства изделий A;

• себестоимость  одного изделия B: 8+0,2X2, где X2 - объем  производства изделий B.

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

Как отмечено выше, объемы производства изделий A и B обозначены через переменные X1 и X2.

Составим  целевую функцию задачи, выражающую прибыль от производства изделий. Будем  считать, что прибыль от продажи  одного изделия представляет собой  разность его цены и себестоимости. Прибыль от продажи одного изделия A можно выразить следующей формулой: 12-(7+0,2X1) = 5-0,2X1. Аналогично выразим прибыль  от продажи одного изделия B: 10-(8+0,2X2) = 2-0,2X2. Таким образом, целевая функция  задачи (прибыль от продажи всех изделий A и B) имеет следующий вид:

E = (5-0,2X1)X1 + (2-0,2X2)X2 = 5X1 - 0,2X12 + 2X2 - 0,2X22→ max.

Приведем  математическую модель задачи:

13X1 + 6X2 ≤ 90

8X1 + 11X2 ≤ 88

X1, X2 ≥ 0

X1, X2 - целые 

E = 5X1 - 0,2X12 + 2X2 - 0,2X22→ max.

Здесь ограничения  устанавливают предельный расход платины  и палладия.

В этой задаче система ограничений линейная, а  целевая функция - нелинейная (квадратичная). Таким образом, данная задача представляет собой задачу нелинейного квадратичного  программирования.

2.2. Решение  задачи методом Франка-Вульфа

Предварительно  найдем градиент целевой функции:

 

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

13X1 + 6X2 ≤ 90

8X1 + 11X2 ≤ 88

X1, X2 ≥ 0

E = 5X1 + 2X2 →  max.

Решив эту  задачу, получим начальное допустимое решение: X1(0)=6,923,

X2(0)=0. Найдем  значение целевой функции для  этого решения: E(0) = 5·6,923 - -0,2·6,9232 + 2·0 - 0,2·02 = 25,03.

Необходимо  также задать требуемую точность решения задачи (ε). Зададим ее равной 500 ден.ед., т.е. будем считать, что решение найдено, если переход к новому решению приводит к увеличению целевой функции не более чем на 500 ден.ед. В данной задаче целевая функция выражается в тысячах ден.ед., поэтому ε=0,5.

Решим задачу, используя итерационный алгоритм на основе метода Франка-Вульфа.

Итерация 1

1. Определяется  градиент целевой функции в  точке ОДР, соответствую-

щей текущему решению:

grad E (X(0))= (5-0,4·6,923; 2-0,4·0) = (2,2; 2).

2. Определяется  угловая точка ОДР, соответствующая  предельно допустимому (без нарушения  ограничений) перемещению от текущего  решения в направлении градиента.  Для этого решается задача  линейного программирования исходной  системой ограничений и целевой  функцией, коэффициентами которой  являются координаты градиента: 

13X1 + 6X2 ≤ 90

8X1 + 11X2 ≤ 88

X1, X2 ≥ 0

W = 2,2X1 + 2X2 →  max.

Решение этой задачи следующее: X1*=4,863, X2*= 4,463. Это  означает,

что поиск  нового решения будет выполняться  в направлении от точки X(0) =

= (6,923; 0) к  точке X*= (4,863; 4,463).

3. Составляются  уравнения для перехода к новому  решению: 

X1(1) = X1(0) +λ(X1* − X1(0) ) ;

X2(1) = X2(0) +λ(X2* − X2(0) ) ,

где λ –  коэффициент, задающий величину перемещения  от текущего решения к новому решению  в направлении точки X*. Этот коэффициент  определяется на следующем шаге.

Для рассматриваемого примера эти уравнения имеют  следующий вид:

X1 (1) = 6,923 + λ(4,863-6,923) = 6,923 – 2,06λ; 

X2 (1) = 0 + λ(4,463-0) = 4,463λ. 

4. Определяется  коэффициент λ. Этот коэффициент  находится таким образом, чтобы  переход к новому решению обеспечивал  максимальное значение целевой  функции. С этой целью уравнения  для перехода к новому решению,  построенные на шаге 3, подставляются  в целевую функцию E. В результате  целевая функция представляется  как функция от коэффициента  λ: 

E = 5(6,923 –  2,06λ) - 0,2(6,923 – 2,06λ)2 + 2·4,463λ - 0,2(4,463λ)2 =

= -4,8 λ2 + 4,3 λ  + 25.

Значение  λ находится из условия экстремума целевой функции, т.е. из условия dE/dλ=0: dE/dλ=-9,6λ + 4,3 = 0. λ=0,448.

5. Из уравнений,  составленных на шаге 3, определяется  новое решение: 

X1 (1) = 6,923 –  2,06·0,448 = 6;

X2 (1) = 4,463·0,448 = 2.

Определяется  значение целевой функции для  полученного решения:

E(1) = 5·6 - 0,2·62 + 2·2 - 0,2·22 = 26.

6. Проверяется  условие окончания поиска решения.  Для этого определяется разность  значений целевой функции для  нового и предыдущего решения:  ΔE = E(1) −E(0) = 26−25,03 =0,97. Эта величина  сравнивается с заданной точностью  ε. Если ΔE ≤ ε, то текущее  решение принимается в качестве  оптимального. В данном случае ΔE = 0,97, ε = 0,5. Таким образом, условие окончания поиска решения не выполняется. Требуется следующая итерация.

 

Итерация 2

1. Определяется  градиент целевой функции в  точке ОДР, соответствующей текущему  решению: grad E (X(1))= (5-0,4·6; 2-0,4·2) = (2,6; 1,2).

2. Определяется  угловая точка ОДР, соответствующая  предельно допустимому перемещению  от текущего решения в направлении  градиента. Для этого решается  следующая задача линейного программирования:

13X1 + 6X2 ≤ 90

8X1 + 11X2 ≤ 88

X1, X2 ≥ 0

W = 2,6X1 + 1,2X2 →  max.

Решение этой задачи следующее: X1*=4,863, X2*= 4,463.

3. Составляются  уравнения для перехода к новому  решению: 

X1 (2) = 6 + λ(4,863-6) = 6 – 1,137λ; 

X2 (2) = 2 + λ(4,463-2) = 2 + 2,463λ. 

4. Определяется  коэффициент λ из условия экстремума  целевой функции: 

E = 5(6 – 1,137λ) - 0,2(6 – 1,137λ)2 + 2(2 + 2,463λ) - 0,2(2 + 2,463λ)2 =

= -1,5λ2 + 26.

7 6dE/dλ=-3λ = 0.

λ=0.

5. Из уравнений,  составленных на шаге 3, определяется  новое решение: 

X1(2) = 6 – 1,137·0 = 6;

X2(2) = 2 + 2,463·0 = 2.

Определяется  значение целевой функции для  полученного решения:

E(2) = 5·6 - 0,2·62 + 2·2 - 0,2·22 = 26.

6. Проверяется  условие окончания поиска решения.  Определяется разность значений  целевой функции для нового  и предыдущего решения: 

ΔE = E(2) −E(1) =0. Так как ΔE ≤ ε, оптимальное  решение найдено: X1=6, X2=2. Оптимальное  значение целевой функции E=26.

Таким образом, предприятию следует выпустить 6 изделий типа A и 2 изделия типа B. Такой план производства обеспечит  предприятию максимальную прибыль  в размере 26 тыс ден.ед.

2.3. Решение  задачи средствами электронных  таблиц MS Excel

Предположим, что желательно получить результаты (значения переменных X1 и X2) в ячейках B2 и C2. В ячейке B3 введем формулу целевой  функции: =5*B2-0,2*B2^2+2*C2-0,2*C2^2

В ячейке B4 введем формулу первого ограничения (на расход платины): =13*B2+6*C2

В ячейке D4 введем правую часть этого ограничения: 90.

Аналогично  в ячейке B5 введем формулу ограничения  на расход палладия: =8*B2+11*C2, в ячейке D5 – правую часть этого ограничения 88.

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

Примечание. Значения 0 в ячейках B3-B5 получены автоматически  для начальных значений переменных, равных нулю.

Для решения  задачи из меню “Сервис” выберем элемент  “Поиск решения”. В поле “Установить  целевую ячейку” указывается  ячейка B3, где находится формула  целевой функции. Используя переключатели, необходимо указать, что требуется  установить ячейку B3 “равной максимальному  значению” (так как целевая функция  в этой задаче подлежит максимизации). В поле “Изменяя ячейки” указываются  ячейки, в которых должны находиться значения переменных: B2:C2.

В области  “Ограничения” указываются ограничения. Необходимо ввести ограничения на расход платины и палладия, заданные на рабочем листе, а также ограничение на неотрицательность всех переменных (B2:C2>=0) и ограничение на их целочисленность (в поле “Ссылка на ячейку” указать B2:C2, а в поле знака ограничения выбрать отметку “цел”).

Для решения  задачи следует нажать кнопку “Выполнить”. Рабочий лист с результатами решения  показан на рис. 2.

В ячейках B2 и C2 получены оптимальные значения переменных, в ячейке B3 – оптимальное  значение целевой функции. Эти величины совпадают с результатами, полученными  по методу Франка-Вульфа.

 

Рис.1. Рабочий  лист Excel для решения задачи

 

Рис.2. Рабочий  лист Excel с результатами решения

В ячейках B4 и B5 находятся значения левых частей ограничений. Видно, что на выпуск изделий  будет израсходовано 90 г платины  и 70 г палладия.

 

Заключение

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

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

В практической части работы было рассмотрено решение  задачи нелинейного программирования средствами MS Excel.

 

Список литературы

 

   1.   Кузнецов Ю.Н. и др. «Математическое программирование» Москва, «Высшая школа», 1980 г.

   2.   Максимей И.В., Серёгина В.С. «Задачи и модели исследования операций» Гомель, 1999 г.

   3.   Солодовников А.С. «Введение в линейную алгебру и линейное программирование» Москва, «Просвещение», 1996 г.

   4.   Уолш Б. «Программирование на Бейсике» Пер. с анг. – Москва: Радио и связь, 1998 г.

   5.   Фиакко А., Маккормик Г. «Нелинейное программирование» Пер. С анг. – Москва: Мир, 1988 г.

   6. Д.Хедли. Нелинейное и динамическое программирование. -М.: Мир, 1967.

   7. Г.П.Кюнци, В.Крелле. Нелинейное программирование. -М. : Сов. радио, 1965.