4.3.2. Стандартная форма задачи лп

Точные методы решения задач ЛП ориентированы на каноническую форму записи модели. Однако в геометрических представлениях удобнее стандартная форма. Мы будем понимать под стандартной модель, в которой всефункциональные ограничения имеют вид неравенств ивсепеременные неотрицательные. Как и выше, тип экстремума не имеет существенного значения.

Таким образом, стандатрная форма модели имеет вид

Та же модель в векторно-матричных обозначениях:

L = max

или

Здесь символ / означает “или”. Число переменных при отсутствии неограниченных по знаку переменных не больше Соответственно матрицаи векторимеют меньшие размеры, чем в канонической модели.

Поясним преобразование равенств в неравенства. Пусть в исходной модели имеется q равенств. Решив эту систему уравнений относительно первыхq переменных, получим

Используя эти равенства, исключаем из целевой функции и ограничений, уменьшая тем самым количество переменных наq. Однако число ограничений не изменяется, так как для сохранения неотрицательности исключенных переменных должны выполняться неравенства

Таким образом, все ограничения задачи будут записаны в виде неравенств.

4.4. Упрощение модели

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

Горизонтальное нормирование заключается в таком преобразовании условий модели, которое обеспечивает равенство всех свободных членов (правых частей).

Пусть ограничения задачи имеют вид

Каждое неравенство разделим на свое b_i и умножим на одно и тоже некоторое положительное числоb.Тогда получим

где

а в качестве b можно взять любое натуральное число, в частности, полученное как целая часть среднего:

Так как правые части всех неравенств одинаковы, то, если найдется 2 ограничения, для которых выполняются отношения

ограничение kможно отбросить как лишнее.

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

где

а величину Сможно взять порядка среднего значения изС_j.

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

где

В преобразованной таким способом модели сравним коэффициенты условий при переменных. Если найдется такая пара переменных, для которых выполняются неравенства

то переменную x_rможно исключить, так как она заведомо не войдет в оптимальное решение.

4.5. Основные понятия лп. Свойства задач лп

Множество D={xRⁿ| AXB, X0} называетсядопустимым множеством задачЛП. Иначе говоря, это множество всех решений, удовлетворяющих всем ограничениям задачи. Поэтому форма записи модели не влияет наD.

Любое решение ХDназываютдопустимым решениемзадачи ЛП.

Допустимое решение Х^*является оптимальным для задачи максимизации, если выполняется неравенство

L(X^*)  L(X), XD.

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

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

Пусть условия задачи записаны в стандартной форме

a_ijx_j b_i,

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

Из теории множеств известно, что пересечение выпуклых множеств выпукло (если оно не пустое). В задаче ЛП число неравенств, а, значит, число полупространств, конечно. Их пересечение и дает допустимое множество D. В связи с этим дадим 2 определения.

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

Ограниченноевыпуклое многогранное множество называется выпуклым многогранником.

Характерными примерами выпуклых многогранников являются различные пирамиды и призмы.

Таким образом, допустимое множество задачи ЛП может быть или выпуклым многогранным множеством, или выпуклым многогранником, или пустым. Других вариантов быть не может.

Критерий L=C_jX_j – линейная функция и поэтому удовлетворяет условиям как выпуклости, так и и вогнутости одновременно.

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

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

=Const,

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

Теперь введем понятие разрешимой задачи. Задача ЛП называется разрешимой, если она имеет хотя бы одно оптимальное решение, инеразрешимойв противном случае. Следует обратить внимание на то, что в этом определении не фигурируют допустимые решения, так как их наличие недостаточно для разрешимости задачи, что видно из нижеприводимых утверждений.

При решении задач ЛП возможны только три случая:

1. Условия задачи противоречивы (несовместны), допустимое множество пустое и, следовательно, задача неразрешима.

2. Условия задачи совместны, но допустимое множество неограниченно. Тогда возможны два исхода:

а) если критерий неограничен на этом множестве, то задача неразрешима;

б) если критерий ограничен, то задача разрешима.

3. Условия непротиворечивы и множество является выпуклым многогранником. В этом случае задача всегда разрешима.

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

Если модель задачи представлена в каноническом виде, то можно воспользоваться теоремой Кронекера-Капелли для системы линейных уравнений. Согласно теореме система совместна, если ранги основной и расширенной матриц равны, и несовместна в противном случае. Однако из-за трудоемкости вычисления ранга этот способ не используется, а неразрешимость задачи, если она имеет место, обнаруживается в процессе движения к оптимуму или при анализе результатов.