Мат_модели

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

Теперь с помощью метода искусственного базиса выделим в линейной части допустимый базис так, чтобы в заключительной симплекс-таблице в базис не вошли одновременно переменные, произведение которых в нелинейной части равно 0 (например, u1 и λ1 ). Этого, в зависимости от задачи, можно добиться двумя способами. Можно или следить на каждом шаге симплекс-метода, чтобы указанные пары переменных одновременно не оказались в базисе, или, получив заключительную сим- плекс-таблицу, сделать соответствующую замену базиса. Найденный допустимый базис и будет по теореме Куна-Таккера решением исходной задачи.

Итак, вводим искусственные переменные v1,v2 в первые два урав-

нения линейной части (в остальных выделен базис u1,u2 ,u3 ), так что полу-

чаем систему

из которой выражаем

90

v1 = 32 − 2x − 2λ1 +3λ2 −5λ3 + λ4 ,v2 = 24 − 2 y −λ1 −5λ2 + 4λ3 + λ5 ,

и решаем задачу F = v1 + v2 → min . Исключая базисные переменные v1,v2 из

91

Мы получили заключительную симплекс-таблицу и теперь необходимо сделать замену базиса так, чтобы были выполнены нелинейные ограничения. Для этого мы вводим в базис переменную x и, согласно правилам выбора разрешающего элемента, выводим из базиса u1 . Тем самым, ус-

ловие λ1u1 = 0 оказывается выполненным. Получаем симплекс-таблицу:

Таким образом, выделен допустимый базис и оптимальная точка x* = (6,7) получена.

Задачи для самостоятельного решения

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

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

в) решить задачу с использованием метода искусственного базиса.

92

x +3y ≤ 33, 97. z = (x −24)2 +( y −30)2 → min при x ≥ 0, y ≥ 0 и −6 y + x ≥ −48,

7x −9 y ≤ 21

§2. Задача динамического программирования

Рассмотрим динамическую систему, которая последовательно, за n шагов, переходит из некоторого начального состояния s0 в конечное со-

стояние sn . Промежуточные состояния si определяют состояния системы после i -ого шага. Как правило, состояния системы характеризуются несколькими числами, поэтому предполагается, что si являются векторами с m координатами, т.е. si = (si1, si2 ,K, sim ). Переход системы из состояния

в состояние si определяется параметрами (управлениями) ui (i =1,K, n)

при помощи уравнений состояний

si = Fi (si −1,ui ),

а эффективность каждого шага оценивается функциями fi (si −1,ui ). Таким образом, эффективность всего процесса характеризуется суммой

z0 = f1(s0 ,u1 )+ f2 (s1,u2 )+K+ fn (sn−1,un ),

а задача состоит в том, чтобы выбрать набор управлений u1,u2 ,K,un , оп-

тимизирующий (далее предполагается, что решается задача на максимум) z0 :

Процесс решения разбивается на n шагов, для этого введем функцию

zi (si )= fi+1 (si ,ui+1 )+ fi+2 (si+1,ui+2 )+K+ fn (sn−1,un ), i = 0,K,n −1,

которая характеризует эффективность перехода от состояния si к sn . Последовательно оптимизируя zn−1(sn−1 ), zn−2 (sn−2 ),K, z1 (s1 ), z0 (s0 ) по формулам

(называемым уравнениями Беллмана)

93

z0 (s0 )= max[f1 (s0 ,u1 )+ z1 (s1 )], где s1 = F1(s0 ,u1 ), u1

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

В качестве примера рассмотрим следующую задачу.

Пример 3. Планируется работа двух отраслей производства на 4

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

Решение. Ясно, что динамической системой являются две отрасли, состояния которых si определяются вложенными в них средствами, а

управлениями ui = (ui1,ui2 ) на i -ом году являются средства uik , переданные k -ой отрасли. Так как возвращенные средства распределяются полно-

стью, то имеет место условие si −1 = ui1 +ui2 ui2 = si −1 −ui1 , и фактически за-

дача одномерна. Далее будем считать, что управление на i -ом году определяется числом ui = ui1 , т.е. средствами, выделенными первой отрасли. В

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

si = F(si−1,ui ) =ϕ1 (ui ) +ϕ2 (si−1 −ui ) = 0.1ui +0.3(si−1 −ui ) = 0.3si−1 −0.2ui ,

94

а прибыль на i -ом году равна

f (si−1,ui ) = f1 (ui ) + f2 (si−1 −ui ) = 0.3ui +0.2(si−1 −ui ) = 0.2si−1 −0.1ui .

Решение задачи начинаем с оптимизации функции z3 (s3 ):

Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому, очевидно,

u1* = 0 .

Таким образом, поскольку u1* = u2* = u3* = u4* = 0 , то средства каждый

95

Задачи для самостоятельного решения

Планируется действие двух отраслей производства на 4 года. Начальные ресурсы 10000 у.е. Средства x , вложенные в 1-ую отрасль в начале года, дают в конце года прибыль f1 (x) и возвращаются в размере ϕ1(x). Средства y , вложенные во 2-

ую отрасль в начале года, дают в конце года прибыль f2 (y) и возвращаются в раз-

мере ϕ2 (y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль, если

96

Ответы

97

98

Рекомендуемая литература

1.И.Л. Акулич. Математическое программирования в примерах и задачах. — М.: Высшая школа, 1993.

2.А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра. Математика в экономике: Учебник для вузов, Ч. 1, 2. — М.: Финансы и статистика, 2003.

3.А.В. Браилов, М.Г. Орлова, Ю.Н. Швецов. Математика в экономике: Руководство к решению задач. Аналитическая геометрия. Линейное программирование. Ч. 2. — М.: Финансовая Академия, 1998.

4.В.А. Бабайцев, А.В. Браилов, В.Б. Гисин, С.А. Посашков, С.Л. Семаков, И.Г. Шандра. Сборник задач по курсу математики. — М.: Финансовая Академия, 2001.

5.А.С. Солодовников. Динамическое программирование. Учебное пособие. — М.: Финансовая Академия, 2003.

6.А.С. Солодовников. Задача квадратичного программирования. Учебное пособие. — М.: Финансовая Академия, 2004.

7.В.М. Гончаренко, В.Ю. Попов. Экономические приложения линейного программирования. Учебное пособие. — М.: Финансовая Ака-

демия, 2003.

8.М.С. Красс, Б.П. Чупрынов. Основы математики и ее приложения в экономическом образовании. — М.: Дело, 2002.

9.О.Е. Пыркина, Ю.Н. Швецов. Математика в экономике: Руководство к решению задач по курсу «Математическое программирование». — М.: Финансовая Академия, 2001.

10.М.Г. Орлова, О.Е. Пыркина, Ю.Н. Швецов. Контрольные работы по курсу «Математическое программирование». — М.: Финансовая Академия, 2001.

99