Линейное программирование (Графический метод. Симплексный метод) (стр. 7 )

 

Рисунок 4 – Целевая функция на множестве допустимых решений задачи линейного программирования неограниченно возрастает или неограниченно убывает

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

 

Рисунок 5 – Целевая функция принимает экстремальное значение в любой точке некоторого отрезка: минимальное значение – отрезок АВ, максимальное значение – отрезок CD

Если целевая функция принимает экстремальное значение на отрезке, то задача имеет бесчисленное множество решений, поскольку отрезок содержит бесчисленное множество точек.

Графическим метод решения применяется для неканонических форм задач линейного программирования с двумя переменными. Этапы решения задачи линейного программирования графическим методом рассмотрим на примере

Пример (продолжение примера 1.2)

Построим систему координат. По горизонтальной оси откладывают значения переменной , а по вертикальной – значения переменной .

Этап 1 Строим прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

 

(I)

C

 

0 1 2 3 4 5 6

Рисунок 6 – Многоугольник допустимых решений, исходная линия уровня и вектор задачи

Границей полуплоскости является прямая . Рассмотрим первое уравнение , обозначим его цифрой (I) и выразим переменную через переменную . В результате преобразований получим следующее уравнение прямой . Данная прямая проходит через точки с координатами (0;5) и (6;3). Построим прямую на графике (рис. 6).

Для второго уравнения , обозначенного цифрой (II), выражение переменной через переменную примет следующий вид . Прямая (II) проходит через точки с координатами (3;4) и (4;1). Эту прямую также построим на графике.

Этап 2 Находим полуплоскости, определяемые каждым из ограничений задачи.

Рассмотрим неравенство . Прямая (I) делит всю плоскость на две части и рассматриваемое неравенство определяет только одну из них. Для определения полуплоскости, заданной неравенством возьмем контрольную точку, не принадлежащую прямой (I), с известными координатами, например точку О(0;0). Координаты контрольной точки подставим в неравенство и получим выражение вида . Неравенство выполняется, координаты контрольной точки удовлетворяют ему, следовательно, полуплоскость, которой принадлежит точка О, и определяется исследуемым неравенством . На рисунке полуплоскость, заданную неравенством , отмечаем короткими штрихами.

Аналогично, для исследования неравенства выберем, в качестве контрольной точке, вновь точку О(0;0). После подстановке координат указанной точки, получаем верное неравенство . Неравенство задает ту полуплоскость, которой принадлежит контрольная точка О(0;0). Отметим короткими штрихами допустимую полуплоскость.

Условие неотрицательности переменных требует рассмотрения той части многоугольника решений, которая находится в первой координатной четверти, т. е. выше оси и правее оси .

Этап 3 Находим многоугольник решений как часть плоскости, которая одновременно удовлетворяет требованиям первого, второму неравенства и условию неотрицательности. В нашем случае, это выпуклый многоугольник ОАВС – область допустимых решений данной системы неравенств.

Этап 4 Строим исходную линию уровня . Прямая примет вид. Выразим переменную через переменную и получим равенство . Эта прямая проходит через точки с координатами (0;0) и (3;-2).