7. Задача линейного программирования (злп), различные формы записи.

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

(10.10)

при условиях

(10.11)

(10.12)

   .                                 (10.13)

Функция  (10.10) называется целевой функцией (или линейной формой) задачи (10.10) – (10.13), а условия (10.11) – (10.13) – ограничениями данной задачи.

2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции (10.10) при выполнении условий (10.11) и (10.13), где k = m, s = n.

3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (10.10) при выполнении условий (10.12) и (10.13), где k = 0, s = n.

Каноническая (основная) форма	Стандартная (симметричная) форма			Общая форма
1) ограничения
Уравнения .	Неравенства .			Уравнения и неравенств .
2) условия неотрицательности
Все переменные ,		Все переменные ,		Часть переменных ,  ,  .
3) цель задачи
max F(x) или minF(x)		max F(x) [min F(x)]	max F(x) или min F(x)

Замечание.

max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].

Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них может быть преобразована к форме другой. Совокупность чисел  , удовлетворяющих ограничениям (10.11) – (10.13), называется допустимым решением (или планом).

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

при условиях

                                   ,                   (10.14)

где   – скалярное произведение;   и   – m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы уравнений задачи.

План Х называется опорным планом основной задачи линейного программирования, если система векторов  , входящих в разложение (10.14) с положительными коэффициентами  , линейно независима.

Опорный  план  называется  невырожденным,  если  он  содержит ровно m положительных компонент, в противном случае он является вырожденным.

План  , при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.

 

8. Основы симплекс-метода, исследование случаев неразрешимости.

В основе математического метода получения оптимального решения лежат основные свойства ЗЛП:

1.Не существует локального экстремума отличного от глобального. Если экстремум есть, то он единственный.

2.Множество всех планов ЗЛП является выпуклой многогранной областью (многогранником решения).

3.ЦФ в ЗЛП достигает своего max (min) значения в угловой точке многогранника решения (в вершине). Если ЦФ принимает max решение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.

4.Каждой угловой точке отвечает опорный план ЗЛП (не отрицательное базисное решение соответствующей КЗЛП).

Суть симплекс-метода состоит в том, что вначале получают допустимый вариант, удв. всем ограничениям, но обязательно оптимальный (начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за опред. число этапов. Нахождение начального опорного решения и переход к сл. проводятся на основе применения метода Жордана-Гаусса для сист. линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к др. выбирается при этом на основе критерия оптимальности ЦФ. Этапы:

1. опред-ние какого-либо первоначального допустимого базисного решения сист.

2. переход к нехудшему решению

3. проверка оптимальности допустимого базисного решения

Симплекс-метод с искусственным базисом применяется в тех случаях, когда затруднительно найти первоначальный план опорный план КЗЛП. Этот метод заключается в применении правил симплекс-метода к М-задаче. Она получается из исходной добавлением к левой части векторного уравнения таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных, линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М –достаточно большое число. В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки ∆j теперь будет зависеть от буквы М. Для сравнения оценок нужно помнить, что М- достаточно большое число. В процессе решения М-задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу. Если в оптимальном решении М-задачи хотя бы одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна (задача неразрешима). В случае неразрешимости М-задачи будет неразрешима и исходная задача.

Симплекс-метод с естественным базисом,

Для его применения КЗЛП должна содержать единичную подматрицу M*N. В этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП). Проверка на оптимальность опорного плана происходит с помощью признака оптимальности. Переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса. Полученный новый опорный план проверяется снова на оптимальность и т.д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи, либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ. Признак оптимальности состоит из двух теорем: 1.Если для всех векторов А1,А2,…,Аn системы ограничений выполняется условие ∆j = Zj – Cj ≥ 0, где Zj = ∑ Ci Aij, то полученный опорный план является оптимальным. 2.Если для некоторого вектора, не входящего в базис, выполняется условие ∆j = Zj – Cj < 0, то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая а)Если все компоненты вектора, подлежащего вводу в базис, не положительны , то ЗЛП не имеет решения. б)Если имеется хотя бы одна положительная компонента у вектора, подлежащего вводу в базис, то можно получить новый опорный план.

На основании признака оптимальности в базис вводится вектор Ak , давший минимальную отрицательную величину симплекс-разности: ∆k = min (Zj – Cj), j = 1,‾n.

Чтобы выполнялось условие не отрицательности значений опорного плана, выводится из базиса вектор Ar, который дает минимальное положительное оценочное отношение: Q = min Bi / Aik = Br/Ark, Aik >0, i = 1,m. Строка Arназывается направляющей, столбец Ak и элемент Ark направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам: a’rj = arj / ark, j = 1,n.

Элементы i-той строки: a’ij = (aij ark – arj aik) / ark, i = 1,m, j = 1,n, i ≠ r.

Значения нового опорного плана: b’r = br / ark для i=r; b’i = (bi ark – br aik) / ark для i≠r.

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

9. Графическое решение задачи линейного программирования, особые случаи решения ЗЛП. Если в задаче линейного программирования ограничения заданы в виде неравенств с двумя переменными, то задача может быть решена графически. Графический метод решения ЗЛП состоит из этапов: 1.Стоится многоугольная область допустимых решений ЗЛП. 2.Строится вектор-градиент целевой функции. Начало в т.О(0,0), а вершина в т.(df/dx1; df/dx2)=(C1;C2). 3.Строим линию уровня c1x1+c2x2=a, a=const. Линия уровня это прямая перпендикулярная вектору-градиенту. Передвигаемся в направлении этого вектора. В случае максимизации ЦФ до тех пор, пока не покинет ОДР. Предельная точка ОДР при этом движении и является точкой max ЦФ. 4.Для нахождения координат указанной предельной точки, достаточно решить 2 уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку max. Значение ЦФ найденное в этой точке является max. При минимизации ЦФ линия уровня перемещается в направлении противоположном вектору-градиенту.

Особые случаи решения ЗЛП графически

1. оптимальное решение задачи единственно

2. оптимальное решение существует и не одно

fmax=f(А)=f(B)=f(AB)

3. ф-я-цель не ограничена

4. Если у многоугольника решений нет, то система противоречива, следовательно ЗЛП противоречива