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

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

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

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

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

0,2У( +0,4У2 <0,3, 0 < V, < 1,

0<У2<1,                                                               (6.6.7)

0<У, + У2 <1.

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

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

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

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

Рис. 6.15. Геометрическое решение задачи ЛП


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

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

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

Таким образом, мы получили, что У1 = 0,5, У2 = 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+1,4У23] =1,3,

У,+У2=1,

У23=1,

К-^1'                                                                                       (6.6.8)

У!+У23+0 = 1,

-0Д4У, -0,16У2 -0,1У3 +Х = 0.

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

Таблица 6.4

СП

БП

VI

У2

Уз

1

Г,

1,2

1,4

1

=1,3

У2

1

0

0

=1

Уз

0

1

0

=1

У4

0

0

1

=1

0

1

1

1

=1

г

-0,14

-0,16

-0,1

=0

 

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

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

к, = о,у2 = о, Уз = о, у, = 1,3, У2 = 1,г3 = 1,г4 = о,г = о.

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

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

Таблица 6.5

СП

БП ^^

У\

У1

Уз

1

VI

 

6

 

5

5

13

 

7

 

7

7

14

У2

1

0

0

= 1

Уз

6 7

5 7

5 7

1

~ 14

УА

0

0

1

= 1

0

 

1

 

5

2

1

 

7

 

7

7

14

 

 

1

 

8

1

26

£

 

350

70

70

175

 

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

=0 ,У2                   =0,11 =0,У2 = 1,У3   =1'2=г|-

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

1

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

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

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

Таблица 6.6

БП

СП

К

Уз

I

Уг

5

-1

_ 1

~ 2

 

У2

5

-2

1

~ 2

 

 

-5

1

_ 1

~ 2

 

ГА

0

0

= 1

VI

-5

2

_ 1

~ 2

 

г

1 10

1

50

II

ёК

 

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

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48  Наверх ↑