Допустимых решений задачи линейного программирования

На данном этапе рассматривается критерий .

Для решаемой задачи , .

Отобразим графически требование построением градиента и линии уровня целевой функции.

Градиент представлен (см. рис. 8.2.1) вектором, отложенным от начала координат и определяющим проекцию на ось и на ось .

Прямые, перпендикулярные градиенту, представляют множество точек, для координат которых линейная функция сохраняет постоянное значение. Эти прямые называются линиями уровня.

Градиент задает направление наискорейшего возрастания целевой функции . Перемещая линию уровня параллельно самой себе в направлении градиента, находим точку , которая уже принадлежит ОДР и в то же время является первой при достижении линии уровня этой области. Все остальные точки ОДР при дальнейшем перемещении линии уровня в направлении градиента будут доставлять большее значение целевой функции в сравнении с ее величиной в точке . Поэтому координаты точки определяют минимальное значение критерия на изучаемой ОДР.

Точка образована пересечением прямых IV и II (см.рис.1). Для определения координат этой точки решим систему уравнений:

Решение: .

Минимальное значение .

Передвижение линии уровня по ОДР будет определять все большие значения . Очевидно, в последней точке касания линии уровня и ОДР будет наблюдаться максимальное значение целевой функции . Эта точка обозначена на рис. 8.2.1.

Точка получена пересечением прямых I и III. Решив систему уравнений: ,

получим координаты точки : .

В этой точке целевая функция достигает максимального значений . Соответственно план является оптимальным. Задача имеет единственное решение.

Минимальная прибыль будет получена при реализации на производстве плана . Стоимость товарной продукции при этом плане будет минимальная: .

Всегда ли задача линейного программирования имеет решение и, если решение есть, то всегда ли оно является единственным? Разобраться в этом вопросе могут помочь нижеследующие примеры.

8.2.2.

Найти вектор , удовлетворяющий следующей системе ограничений:

и доставляющей максимум целевой функции:

.

Условие задачи 8.2.2. отличается от условия задачи 8.2.1. отсутствием первого ограничения.

Алгоритм поиска области допустимых значений аналогичен алгоритму, описанному в первой задаче. Исключение первого ограничения привело к тому, что ОДР оказалась не ограниченной (см. рис. 8.2.5).

Рис. 8.2.5. Целевая функция не ограничена

В этом случае можно определить координаты точки , где целевая функция получает минимальное значение:

и .

Найти максимальное значение критерия не удается (целевая функция неограничена): .

8.2.3.

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

Рис. 8.2.6. Область допустимых решений пуста

Постановка этой задачи отличается от условия задачи 8.2.1 значением правой части второго ограничения. Процедура построения первой и третьей прямой, а также определение полуплоскостей, координаты точек которых удовлетворяют этим ограничениям, остается без изменения.

Прямая обозначена на рис. 8.2.6. цифрой 2, и стрелками показана полуплоскость, точки которой удовлетворяют второму ограничению.

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

8.2.4.

Решить задачу линейного программирования

Решение задачи 8.2.4 представлено на рис. 8.2.7. Область допустимых решений (ОДР) совпадает с ОДР задачи 8.2.1.

Поскольку в данной задаче изменен критерий: ,

то градиент будет иметь проекции .

Из графика видно, что линия уровня параллельна прямым I и II. Это означает, что линия уровня совпадет с отрезком при поиске и с отрезком при определении . В этом случае задача имеет не единственное решение, а множество решений, т.е. все точки отрезка будут доставлять максимум целевой функции .

Рис. 8.2.7. Решениями являются точки отрезка АС

8.2.5	Ответ 1.1.	8.2.6	Ответ 1.4
2x1+ x2 8	X=(0, 3)	2x1+ x2 6	X=(0, 1)
x1+2x2 6	zmax=6	-x1+3x2 3	zmax=-2
x1+3x2 3
x1 0 x2 0		x1 0 x2 0
z=- x1+2x2		z= x1-2x2
8.2.7.	Ответ	8.2.8.	Ответ
		3x1+ x2 2
-x1+3x2 2	zmax	x1+ x2 3	zmax
x1-2x2 4
x1 0 x2 0		x1 0 x2 0
z= x1+x2		z=-3x1+x2
8.2.9.	Ответ	8.2.10.	Ответ
x1+ x2 2		2x1- x2 4	X=(3, 2)
x1+2x2 6	Решения	3x1-2x2 2	zmin=28
x1+3x2 3	нет	x1 1 x2 2
x1 0 x2 0		x1 0 x2 0
z=-3x1+ x2		z=12x1-4x2