Находим новые потенциалы. Новые оценки:

D12= -2; D13= -4; D15= -1; D23= -2; D24= -1; D25= -2; D31= -2; D32=0. Поскольку все Dij£0 решение является оптимальным:

33 0 0 7

Xоpt1 = 15 30 0 0

0 0 29 33

Однако, так как оценка клетки D32=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение:

Таблица 3

Находим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого Dmax=D32, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:

3 0 0 37

Xоpt2 = 45 0 0 0

0 30 29 3

Оптимальное распределение инвестиций

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

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере ξ (сотен тыс. рублей) выражается функцией fi(xi). Приходим к задаче fl(xl)+f2(x2)+f3(x3)+f4(x4)àmax , где xi - пока еще неизвестный размер х1+х2+х3+х4≤7; х1,х2,х3.х4≥0 инвестиций i-й фирме. Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для k=2,3 и 4 фирм.

Пусть первым двум фирмам выделено ξ инвестиций. обозначим z2(ξ) величину инвестиций 2-й фирме, при которой сумма f2(z2j)+fl(ξ-z2j), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F2(ξ). Далее действуем также: находим функции z3 и F3 и т.д. На k-ом шаге для нахождения Fk(ξ) используем основное рекуррентное соотношение: Fk(ξ)=max{fkj(хk)+F(k-1)( ξ-хk); 0 ≤ хk ≤ ξ

Таблица 1