Исследование операций. Линейное, динамическое программирование


Здесь фотокиннект сочи. | На сайте web-wip.ru создание одностраничного сайта. |

Исследование операций - часть 52


Чтобы представить себе принципиальную сторону ОЗЛП, обратимся к геометрической интерпретации. Пусть число уравнении т па два меньше числа переменных п (п - т = k =

2). Такой частный случай дает возможность геометрической интерпретации ОЗЛП па плоскости.

Мы знаем, что т линейно независимых уравнении (9.1) всегда можно разрешить относительно каких-то т базисных переменных, выразив их через остальные, свободные, число которых равно п - т = k (в нашем случае k = 2). Предположим, что свободные переменные — это х1 и х2 (если это не так, то всегда можно заново перенумеровать переменные), а остальные: х3, х4,..., хn—базисные. Тогда вместо т уравнений (9.1) мы получим тоже т уравнений, но записанных в другой форме, разрешенных относительно х3, х4,...:

          (9.3)

Будем изображать пару значений свободных переменных точкой с координатами х1, х2 (рис. 9.1). Так как переменные х1, х2 должны быть неотрицательными, то допустимые значения свободных переменных лежат только выше оси Ox1 (на которой х2 = 0) и правее оси Ох2 (на которой х1

= 0). Это мы отметим штриховкой, обозначающей «допустимую» сторону каждой оси.

Теперь построим па плоскости х10х2

область допустимых решений или же убедимся, что ее не существует. Базисные переменные х3,x4, ..., xn тоже должны быть неотрицательными и удовлетворять уравнениям (9.3). Каждое такое уравнение ограничивает область допустимых решений. Действительно, положим

в первом уравнении (9.3) х3 = 0; получим уравнение прямой линии:

На этой прямой х3 =0; по одну сторону от нее х3 >0, по другую — х3

< 0. Отметим штриховкой ту сторону (полуплоскость), где х3 > 0 (рис. 9.2). Пусть эта сторона оказалась правее и выше прямой х3

= 0. Значит, вся область допустимых решений (ОДР) лежит в первом координатном угле, правее и выше прямой х3

= 0. Аналогично поступим и со всеми остальными условиями (9.3). Каждое из них изобразится прямой со штриховкой, указывающей «допустил1ую» полуплоскость, где только и может лежать решение (рис. 9.3).




Содержание  Назад  Вперед