Материал: 5021

11

Систему привели к системе с базисом:

Базисное решение X (8, 0, 0, -10) не является опорным.

Пример 2. Дана каноническая система:

где x2 , x3 , x4 – базисные неизвестные, свободные члены неотрицательны. Если свободные неизвестные x1 , x5 прировнять к нулю, то получим

базисное неотрицательное решение, которое называется опорным. Итак, X1 (0; 2; 3;1; 0) – опорное решение.

Для нахождения других опорных решений выполняем операцию однократного замещения, при этом:

1)разрешающий столбец выбираем так, чтобы в нем оказался хотя бы один положительный элемент;

2)разрешающую строку выбираем по наименьшему Ө, который равен отношению свободных членов к положительным элементам разрешающего столбца.

X2 (1/ 3; 5 / 3; 3; 0; 0) – опорное решение.

Можно найти и другие опорные решения, например, в качестве разрешающего столбца можно выбрать столбец соответствующий x5 .

Решить системы методом Жордана – Гаусса. Если система имеет множество решений, найти базисное.

12

Найти все опорные решения следующих систем.

13

3. ГРАФИЧЕСКИЙ МЕТОД

Графически решаются задачи в стандартной форме, содержащие не более двух переменных; задачи общего вида, в системе ограничений которых не более двух свободных неизвестных.

Рассмотрим примеры.

Пример 1. Решить графически задачу линейного программирования.

Z 3x1 x2 max

Строим область решений системы ограничений. Для этого последовательно определяем области решений каждого неравенства.

Чтобы найти область решений первого неравенства, строим граничную прямую x1 x2 2 , которая делит плоскость на две полуплоскости, а затем, испытывая какую-либо точку (проще О(0;0)), определяем полуплоскость, точки которой удовлетворяют неравенству. Точка О(0;0) не удовлетворяет неравенству x1 x2 2 , следовательно, область решений неравенства не включает начала координат. Отмечаем область стрелками.

Решаем аналогично остальные неравенства, находим общую область решений, удовлетворяющую всем неравенствам.

14

Областью решений системы неравенств является многоугольник АВСДЕМ. Так как решения удовлетворяют условиям x1 0, x2 0 , область решений называется допустимой областью решений задачи.

В этой же системе координат строим целевой вектор n (3,1) , перпендикулярный к линиям уровня Z 3x1 x2 . Строим перпендикулярно вектору линию уровня и, перемещая ее параллельно самой себе в направлении вектора n , определим крайнюю точку области, в которой Z примет наибольшее значение.

В решаемой задаче максимальное значение Z будет достигнуто в точке Е. Определяем координаты этой точки:

Приводим систему к системе с базисом:

Перейдем от канонической системы к стандартной, отбрасывая в уравнениях базисные переменные.

15

x2 2x3 4, x3 1.

Исключаем базисные переменные из выражения для функции Z

Решаем графически задачу:

Z 13 2x2 2x3 max x2 2x3 4,

x3 1, x2 0, x3 0.

Максимальное значение функции Z достигается в точке А(4;0):

Zmax 13 8 21.

Найдем оптимальное значение x1 , x4 :

Ответ: Zmax 21, X (0, 4, 0,1) .

Решить графически следующие задачи линейного программирования: