6.6. Графическое решение задачи

Чтобы решить задачу графически, сведем ее к двум перемен­ным У\ и У₂. Для этого найдем из пятого ограничения (6.6.5) пе­ременную Кз = 1 - У\ - У₂ и подставим в (6.6.4) и в (6.6.5). Полу­чим следующую задачу.

Максимизировать функцию

X = 0,04 У\ + 0,06 У2 + 0,1                                               (6.6.6)

при ограничениях

0,2У₍ +0,4У₂ <0,3, 0 < V, < 1,

0<У₂<1,                                                               (6.6.7)

0<У, + У₂ <1.

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

В системе координат У\0У₂ строим многоугольник О А ВС (рис. 6.15), который является областью допустимых решений системы неравенств, т.е. любая точка (У\, У₂) лежащая на контуре или внутри области О А ВС удовлетворяет системе неравенств (6.5.7). Далее строим вектор С (0,04; 0,06), отвечающий функции г, который показывает направление быстрейшего возрастания функции г.

Затем проводим линию уровня Z = 0,04К] + 0,06 Кг + 0,1 = 0,1. Она проходит через начало координат и перпендикулярна вектору С .

Перемещаем линию уровня z = 0,1 в направлении вектора С до тех пор пока она не пройдет через одну из вершин многоуголь­ника ОАВС так, что он весь будет лежать под линией уровня. Это вершина В. В ней функция X достигает максимального значения.

Найдем координаты точки В, для чего решим систему

У,+У₂=1, 0,2У₁+0,4У₂=0,3.

Из решения этой системы находим, что У_х = 0,5 и У₂ = 0,5, тогда г = 0,04 • 0,5 + 0,06 • 0,5 + 0,1 = 0,15.

Таким образом, мы получили, что У₁ = 0,5, У₂ = 0,5, Уз = 0 и максимальное значение доходности равно 0,15 или 15%.

6.6.3. Симплексный метод решения задачи

Рассмотрим симплексное решение задачи (6.6.4) — (6.6.5). К левой части первых четырех неравенств системы (6.6.5) прибав­ляем базисные переменные У, > 0 (/ = 1,2,3,4) и записываем систе­му (6 6.4) — (6.6.5) в виде системы уравнений

1,2У₁+1,4У₂+У₃+¥_] =1,3,

У,+У₂=1,

У₂+У₃=1,

К-^¹'                                                                                       (6.6.8)

У!+У₂+У₃+0 = 1,

-0Д4У, -0,16У₂ -0,1У₃ +Х = 0.

Эту систему решаем с помощью укороченных симплексных таблиц. Систему уравнений (6.6.8) записываем в виде табл. 6.4.

 

В первый столбец записываем базисные переменные, а в пер­вую строку — свободные переменные. Последний 1 -й столбец яв­ляется столбцом свободных коэффициентов системы (6.6.8). Под столбцами переменных У_ъ У₂, Уз стоят коэффициенты при этих неизвестных. Тогда ясно, что по строкам таблицы записаны урав­нения системы (6.6.8).

Полагая свободные переменные равными нулю, из табл. 6.4 получаем первое допустимое решение системы (6.6.8)

к, = о,у₂ = о, Уз = о, у, = 1,3, У₂ = 1,г₃ = 1,г₄ = о,г = о.

Далее решение улучшаем, пользуясь следующим правилом.

В Z-cтpoкe выбираем наименьшее отрицательное число — 0,16, ему соответствует разрешающий столбец У₂. Элементы 1-столбца делим на соответствующие элементы К₂-столбца и наименьшее положительное отношение соответствует разрешающей У]-стро­ке. На пересечении разрешающей строки и разрешающего столб­ца стоит разрешающий элемент 1,4. Совершаем шаг обыкновен­ного жорданова исключения (ШОЖИ) с разрешающим элемен­том 1,4. Переходим к табл. 6.5 по следующему правилу. Меняем местами У! и У₂. На месте разрешающего элемента стоит величи­на обратная. Элементы разрешающей строки делим на разреша­ющее число. Элементы разрешающего столбца делим на разре­шающее число и меняем знак. Остальные элементы находим по правилу прямоугольника: старый элемент минус дробь, где в чис­лителе стоит произведение соответствующего элемента в разре-

 

тающем столбце на соответствующий элемент в разрешающей строке, а в знаменателе стоит разрешающий элемент. Получаем из табл. 6.5 новое улучшенное допустимое решение

=0 ,У₂                   =0,11 =0,У₂ = 1,У₃   ⁼¹'²⁼г|-

Так как в 2-строке имеется отрицательный элемент, то по ука-

1

занному правилу находим разрешающий элемент — и совершаем

ШОЖИ с разрешающим элементом ~. При перемене У\ и 0,

0-сголбец не пишется, так как коэффициенты под ним равны нулю. Получаем табл. 6.6.

 

Так как в г-строке и 1-столбце нет отрицательных элементов, то получили оптимальный план.

Оптимальный план содержит только активы А и В. И при этом У\ = У₂ = 0,5, а Х_тах =0,15, или 15%.

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

Если бы у нас было 200 переменных, существовало бы 200 урав­нений с 200 неизвестными. Задача стала бы чрезвычайно трудной. Однако, компьютерные версии симплексного алгоритма очень эффективны и могут скрупулезно и эффективно решать задачи, включающие сотни переменных и ограничений.