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

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

 

 

 

 

Оглавление

Введение 3

Глава I. Постановка задачи. Методы решения 5

1.1. Постановка  задачи математического программирования 5

1.2. Методы  решения 7

1.2.1. Градиентные  методы 7

1.2.2 Методы  Монте-Карло 8

1.2.3. Методы  выпуклого программирования 9

1.2.4. Теорема  Куна-Таккера 10

1.2.5. Квадратичное  программирование. Метод Вулфа-Фрэнка 12

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

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

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

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

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

Заключение 27

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

 

Введение

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

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

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

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

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

Цель работы: показать некоторые особенности  методов нелинейного программирования.

Объект исследования: нелинейное программирование

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

 

Глава I. Постановка задачи. Методы решения

1.1. Постановка  задачи математического программирования

Задачи математического  программирования формулируются следующим  образом: найти экстремум некоторой  функции многих переменных f (x1, x2,…, xn) при ограничениях gi (x1, x2,…, xn) bi, где gi – функция, описывающая ограничения, а bi – действительное число, i = 1,…, m. Функция f называется функцией цели (целевой функцией).

В общем, виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f(x1, x2, …, xn) при условии, что ее переменные удовлетворяют соотношениям:

 

где f и g – некоторые известные функции n переменных, а bi – заданные числа.

В результате решения задачи будет определена точка Х*= (x1*, x2*, …, xn*), координаты которой удовлетворяют соотношениям и такая, что для всякой другой точки Х= (x1, x2, …, xn), удовлетворяющей условиям, выполняется неравенство f (x1*, x2*, …, xn*) ≥ f (x1, x2, …, xn) [f (x1*, x2*, …, xn*) ≥ f (x1, x2, …, xn)].

Если f и gi – линейные функции, то задача является задачей линейного программирования.

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

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

Если определена область допустимых решений, то нахождение решения задачи сводится к определению  такой точки этой области, через  которую проходит гиперповерхность наивысшего (наименьшего) уровня: f (x1, x2, …, xn) = h. Указанная точка может находиться как на границе области допустимых решений, так и внутри неё.

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

 

1.2. Методы  решения 

1.2.1. Градиентные  методы

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

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

Например, если нужно решить систему уравнений 

(X2+1)(Y-1)=3,Y=ln(X+1),

то  можно заменить эту задачу задачей  минимизации функции F(X,Y)=[(X2+1)(Y-2)-3]2+[Y-ln(X+1)]2 (если система имеет решение, то искомый минимум равен нулю).

Градиент  этой функции определяется вектором

Grad F(X,Y) = {2[(X2+1)(Y-2)-3] 2X (Y-2) - 2[Y-ln(X+1)]/(X+1),

2 [(X2+1)(Y-2)-3](X2+1) - 2[Y-ln(X+1)]}.

Выбираем  начальную точку M0(2,1) и шаг h=1.Здесь  значение функции F(M0)=64, градиент в этой точке grad F(M0) =[64.066, -80.197], нормированный градиент (вектор единичной длины, составленный из компонент, деленных на корень из суммы их квадратов) gradн F(M0) = [0.62, -0.78]. Смещаемся в направлении, обратном градиенту (ищем минимум), с выбранным шагом в точку М1=М0-h gradн F(M0)=(2-1 0.62, 1+1 0.78)=(1.38, 1.78) и обнаруживаем, что F(M1)=14 < F(M0).

Аналогичный переход с учетом gradн F(M1) = [0.19, -0.98] приводит в точку М2(1.19, 2.76), где F(M2) 5.26, gradн F(M2) = [-0.96, -0.27]. Переход в очередную точку М3(2.15, 3.03) дает F(M3) 11.33 > F(M2).Соответственно уменьшаем шаг вдвое (h=0.5) и получаем точку М4(2.15, 3.03), где F(M4)=3.78, gradн F(M2) = [0.12, 0.99]. Очередной переход приводит в точку с большим значением функции и приходится еще уменьшать шаг и т.д.

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

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

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

 

1.2.2 Методы  Монте-Карло

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

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

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

 

1.2.3. Методы  выпуклого программирования

Эти методы реализуют  поиск минимума выпуклой функции  или максимума вогнутой на выпуклом множестве планов. Если множество  планов - выпуклый многогранник, то эти  методы допускают использование  симплексного метода.

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

F(X1, X2, .. ,Xn) = f1(X1) + f2(X2) + ... + fn(Xn).

При решении  многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.

Пусть требуется  найти экстремумы функции F(X) при  условиях fi(X)=0 (i = 1 .. m).

Функция называется функцией Лагранжа и коэффициенты li - множителями Лагранжа.

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

Например, при  поиске максимума F(X1, X2) = X1+X2 при единственном условии X12+X22=1 строится функция Лагранжа

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

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

 

1.2.4. Теорема  Куна-Таккера

Пусть стоит  задача минимизации F(X) при условиях:

 

где X - n-мерный вектор, F(X) и fi(X) - выпуклые функции, что обеспечивает выпуклость множества планов и единственность искомого минимума (напомним, что мы считаем функцию выпуклой в некоторой точке, если главные миноры матрицы вторых производных положительны).

Введем функцию  Лагранжа

 

Теорема Куна-Таккера утверждает, что вектор X*³0 является решением поставленной задачи тогда и только тогда, когда существует вектор l* ³0 такой, что при всех X ³ 0, l³0

Так как функция  Лагранжа в точке (X*, l*) принимает минимум по X и максимум по l, то эта точка называется седловой и эта теорема называется теоремой о седловой точке или теоремой о минимаксе.

Достаточность условий этой теоремы доказывается сравнительно просто. Доказательство их необходимости предполагает выполнение условий регулярности, т.е. существования  хотя бы одной допустимой точки X, где  fi(X) < 0 при всех i.

Если F(X) и  fi(X) дифференцируемы, то условия теоремы эквивалентны «локальным» условиям, утверждающим, что в точке (X*, l*)

 

Остановимся на частных случаях задачи.

Если в  поставленной задаче отсутствуют требования неотрицательности (2), то путем замены X разностью двух неотрицательных векторов можно показать, что условие (5) упрощается к виду (если нет требования неотрицательности для одной из компонент X, то обратится в нуль производная Ф(X) по соответствующей переменной).

Если fi(X) = 0 при некотором i, то заменой этого равенства системой неравенств fi(X) £ 0, -fi(X) £ 0 обнаруживаем, что в (6) соответствующая производная обращается в нуль и исчезает условие неотрицательности по i; если fi(X) = 0 при всех i, то (6) упрощается к виду

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

Так при минимизации CTX при условиях AX ³ B, X ³ 0 функция Лагранжа имеет вид

Ф(X, l) = CTX + lT(AX - B)

и условия  Куна-Таккера

 

Отсюда получаем с учетом XTC = CTX, lTB = BTl, XTAT l = lTAX, что в седловой точке достигается минимум по X и максимум по , причем

CTX = BTl,

AX ³ B, ATl £ C,

X ³ 0, l ³ 0.

 

1.2.5. Квадратичное  программирование. Метод Вулфа-Фрэнка

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

 

где A - матрица  размерности m на n , C, X - n-мерные векторы, B - m-мерный вектор, D - положительно-определенная n-мерная квадратная матрица (матрица называется положительно определенной, если положительны ее главные миноры). Так целевая функция

 

представится  в виде (1), где 

 

Положительная определенность матрицы D и линейность ограничений (множество планов выпукло) позволяют использовать теорему  Куна-Таккера.

Функция Лагранжа здесь имеет вид:

 

и условия  Куна-Таккера приводятся к форме:

 

Если ввести векторы ослабляющих переменных, то (4) - (5) примут вид:

 

С учетом неотрицательности переменных можно поставить задачу минимизации (до нуля) функции

 

 

при условиях

 

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

 

то (7) - (9) приведутся к виду:

 

где

Метод П.Вулфа  и М. Фрэнка сводит решение задачи к форме, допускающей применение симплексной процедуры.

Здесь отыскивается некоторый опорный план W0. Если g(W0) = 0, то этот план оптимален. В противном случае отыскивается градиент

 

и его компоненты на один шаг симплексного преобразования (перехода к другому опорному плану) принимаются за коэффициенты "линейной формы". После выбора нового опорного плана выполняются вышеописанные  рассуждения.

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

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

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.