Формы злп

Форма задачи линейного программирования, у которой ограничения заданы в виде неравенств, называется стандартной, а форма задачи, у которой ограничения заданы в виде уравнений –канонической. Если же система ограничений содержит и уравнения и неравенства, то такая форма называетсясмешанной.

Стандартная	Каноническая	Смешанная
		, ,

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

Если задача содержит только две переменные, а система ограничений задана в виде неравенств, то её можно решить графическим методом.

Графический метод решения ЗЛП состоит из следующих этапов.

1. Строится область допустимых решений (ОДР).

2. Строится вектор-градиент целевой функции (вектор, координатами которого являются частные производные функции) с приложением в начале координат – .

3. Линия уровня C₁x₁+C₂x₂ = а (а – постоянная величина) - прямая, перпендикулярная вектору–градиенту – передвигается в направлении этого вектора в случае максимизацииf(x_1,x₂)до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимумаf(x_1,x₂).

4. Для нахождения ее координат достаточно решить систему из двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x_1,x₂),найденное в полученной точке, является максимальным.

При минимизации f(x_1,x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то целевая функцияf(x_1,x₂) не ограничена на максимум (в задаче максимизации) или минимум (в задаче минимизации).

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

Пример. Найти максимальное значение функцииf=2x₁ + 3x₂при условиях

Построим область допустимых значений:

1) первое ограничение x_+3x_18;прямаяx_+3x_=18пересекает оси координат в точках06180; неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка 000+3*0<18 принадлежит полуплоскости);

2) второе ограничение 2x_+x_16: прямая2x_+x_=16пересекает оси координат в точках01680; неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка002*0+ 0<16 принадлежит полуплоскости);

3) неравенству x_5 соответствует полуплоскость, содержащая прямуюx_=5 и лежащая ниже неё.

4) x₁0правее ОX_;

5) x₂0выше ОX₁.

Вектор-градиент имеет координаты .

Построим линии уровня 2x_+ 3x_ = а. При а =0 получим прямую2x_+3x_ =0, проходящую через начало координат, перпендикулярно вектору-градиенту. Так как задача на максимум, то передвигаем линию уровня в направлении градиента. Предельной точкой (последней из области допустимых решений, с которой соприкасается линия уровня) является точка С. Значит, в ней достигается максимум функцииf (рис. 1).

Найдём её координаты. Для этого решим систему, составленную из уравнений прямых пересекающихся в точке С (IиII):

Таким образом, получим x_6, x₂4, f_max 2*6+3*4=24.

Рис. 1.