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У2+У3+¥] =1,3,
К-^1' (6.6.8)
-0Д4У, -0,16У2 -0,1У3 +Х = 0.
Эту систему решаем с помощью укороченных симплексных таблиц. Систему уравнений (6.6.8) записываем в виде табл. 6.4.
Таблица 6.4
|
В первый столбец записываем базисные переменные, а в первую строку — свободные переменные. Последний 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
|
тающем столбце на соответствующий элемент в разрешающей строке, а в знаменателе стоит разрешающий элемент. Получаем из табл. 6.5 новое улучшенное допустимое решение
=0 ,У2 =0,11 =0,У2 = 1,У3 =1'2=г|-
Так как в 2-строке имеется отрицательный элемент, то по ука-
1
занному правилу находим разрешающий элемент — и совершаем
ШОЖИ с разрешающим элементом ~. При перемене У\ и 0,
0-сголбец не пишется, так как коэффициенты под ним равны нулю. Получаем табл. 6.6.
Таблица 6.6
|
Так как в г-строке и 1-столбце нет отрицательных элементов, то получили оптимальный план.
Оптимальный план содержит только активы А и В. И при этом У\ = У2 = 0,5, а Хтах =0,15, или 15%.
Как можно видеть, симплексный метод выражает алгебраически процесс перехода от вершины к вершине области возможных решений, где движение всегда предпринимается в направлении увеличения величины целевой функции (заметьте, что существуют случаи исключений, в которых величине целевой функции позволяется оставаться постоянной при шаге). Преимущество переключения с геометрии на алгебру состоит, конечно, в том, что алгебра действует при 200 измерениях так же, как и при двух, а графические изображения представить гораздо сложнее.
Если бы у нас было 200 переменных, существовало бы 200 уравнений с 200 неизвестными. Задача стала бы чрезвычайно трудной. Однако, компьютерные версии симплексного алгоритма очень эффективны и могут скрупулезно и эффективно решать задачи, включающие сотни переменных и ограничений.
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 Наверх ↑