Методы решения задач нелинейного программирования

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

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

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

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

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

grad E = =(5-0,4X1, 2-0,4X2).

Найдем также начальное допустимое решение. В качестве такого решения можно использовать любой набор значений 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.

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

Решение этой задачи следующее: X*1 =4,863, X*2 = 4,463. Это означает, что поиск нового решения будет выполняться в направлении от точки X(0)= =(6,923; 0) к точке X*= (4,863; 4,463).

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

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

X2(1) =X(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.

Примечания:

1.     Если значение λ, найденное из уравнения dE/dλ=0, оказывается больше единицы, то принимается λ=1. Это означает, что экстремум целевой функции в направлении, задаваемом градиентом, находится за пределами ОДР. В этом случае новое решение должно находиться на границе ОДР (т.е. в точке X*), но не выходить за нее.

2.     Если уравнение dE/dλ=0 не имеет решений (например, не зависит от λ), то также принимается λ=1.

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.

f = 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.

dE/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 тыс ден.ед.

Примечания:

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

2.      В рассмотренном примере решалась задача с целевой функцией, подлежащей максимизации. Если требуется минимизация целевой функции, то задача решается точно так же. Единственное отличие состоит в том, что целевая функция W в задаче, решаемой на шаге 2,также подлежит минимизации

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

      Рассмотрение общей постановки задачи нелинейного программирования;

      Описание графического метода решения задач нелинейного программирования;

      Описание метода множителей Лагранжа для решения задач нелинейного программирования;

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

      Рассмотрение на примерах методов решения задач нелинейного программирования.

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

СпиСОК ИСПОЛЬЗуемых ИСТОЧНИКОВ

1.                   Бодров В.И Математические методы принятия решений / В.И. Бодров, Т.Я. Лазарева, Ю.Ф. Мартемьянов. – Тамбов: Издательство ТГТУ, 2004. – 83 с.

2.                   Самаров К. Л. Функции нескольких переменных. Нелинейное программирование / К. Л. Самаров. – М. : ООО «Резольвента», 2009. – 26 с.

3.                   Исследование операций в экономике / под. ред. Н.Ш. Кремера . – М. : Юнити, 2000. – 408 с.

4.                   Ковалев В.В. Финансовый анализ: методы и процедуры / В.В. Ковалев. – М.: Финансы и статистика, 2002. – 560 с.

5.                   Смородинский С.С. Оптимизация решений на основе методов и моделей математического программирования / С.С. Смородинский, Н.В. Батин. – Минск: БГУИР, 2003. – 136 с.

19