7. Формы записи задач линейного программирования.

8. Экономическая интерпритация задачи линейного программирования.

Как отмечено выше, среди широкого класса задач оптимального

программирования имеются важные подклассы задач,

для которых разработаны эффективные методы решения.

Наиболее изученным подклассом задач являются задачи

линейного программирования.

В задаче линейного программирования (ЗЛП) требуется

найти экстремум (максимум или минимум) линейной целевой

функции fix):

кретной ЗЛП возможно ограничение типа равенства или

неравенства (в ту или иную сторону).

Систему ограничений (2.10) называют функциональными

ограничениями ЗЛП, а ограничения (2.11) — прямыми.

Вектор X = (Х1, X2, ..., хп),

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

(2.10), (2.11), называется допустимым решением,

или планом ЗЛП, т.е. ограничения (2.10), (2.11) определяют

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

программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум

или минимум целевой функции (2.9), называется оптимальным

планом (оптимальным решением) ЗЛП.

Канонической формой записи задачи линейного программирования

(КЗЛП) называют задачу вида (запись с использованием

знаков суммирования):

Матричная форма записи КЗЛП:

9. В чем заключается геометрическая интерпритация лп.

Рассмотрим эту задачу на плоскости, т.е. при га = 2.

Пусть система неравенств (2.19), (2.20) совместна (имеет хотя

бы одно решение):

Каждое неравенство этой системы геометрически определяет

полуплоскость с граничной прямой аi1х1+аi2х2=bi, где

i = 1,m. Условия неотрицательности определяют полуплоскости

соответственно с граничными прямыми х\ = 0, х2 = 0.

Система совместна, поэтому полуплоскости, как выпуклые

множества, пересекаясь, образуют общую часть, которая является

выпуклым множеством и представляет собой совокупность

точек, координаты каждой из которых составляют

решение данной системы. Совокупность этих точек называют

многоугольником решений. Это может быть точка, отрезок,

луч, замкнутый многоугольник, неограниченная многоугольная

область.

Если в системе ограничений (2.19) - (2.20) га = 3, то каждое

неравенство геометрически представляет полупространство

трехмерного пространства, граничная плоскость которого

аi1х1+аi2х2+аi3х3=bi а условия неотрицательности — полупространства

с граничными плоскостями соответственно

Xj = 0 (j=l,2,3). Если система ограничений совместна, то

эти полупространства, как выпуклые множества, пересекаясь,

образуют в трехмерном пространстве общую часть, которая

называется многогранником решений.

Пусть в системе (2.19) - (2.20) га > 3, тогда каждое неравенство

определяет полупространство га-мерного пространства

с граничной гиперплоскостью аi1х1+аi2х2+… аiпхп=bi

i - 1, т , а условия неотрицательности — полупространства с

граничными гиперплоскостями хj = 0, j = 1, п.

Если система ограничений совместна, то по аналогии с

трехмерным пространством она образует общую часть п-

мерного пространства, называемую многогранником решений,

так как координаты каждой его точки являются решением.

Таким образом, геометрически ЗЛП (2.19)-(2.20) представляет

собой поиск такой точки многогранника решений,

координаты которой доставляют линейной функции наибольшее

(наименьшее) значение, причем допустимыми решениями

являются все точки многогранника решений.

10. Основные этапы графическго метода решения задачи линейного программирования.

Если в ЗЛП ограничения заданы в виде неравенств с двумя

переменными, она может быть решена графически. Графический

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

Этап 1. Сначала на координатной плоскости х10х2 строится

допустимая многоугольная область (область допустимых

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

Далее строится вектор-градиент линейной функции

f(X) в какой-нибудь точке x0 , принадлежащей допустимой

области:

Этап 2. Прямая С1Х1+С2Х2= f(x0), перпендикулярная вектору-

градиенту, передвигается в направлении этого вектора

в случае максимизации f(X) до тех пор, пока не покинет

пределов многоугольной области. Предельная точка (или

точки) области при этом движении и является точкой максимума

f(X).

Этап 3. Для нахождения координат точки максимума

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

соответствующих ограничений и дающих в пересечении

точку максимума. Значение f(X), найденное в получаемой

точке, является максимальным.

В случае минимизации f(X) прямую С1Х1+С2Х2= f(x0),

надо двигать в направлении, противоположном вектору-градиенту.

Ясно, что если прямая при своем движении не покидает

допустимой области, то соответствующий максимум

или минимум f(X) не существует.