 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Канонические формы постановки ЗЛП
ЗЛП, заданной в канонической форме, называется задача, в которой необходимо найти оптимум линейной формы
|
при ограничениях–равенствах:
|
|
Если целевая функция F исследуется на экстремум типа минимум, то говорят, что задача задана в первой канонической форме, если на экстремум типа максимум – вовторой.
Определение. Набор чисел 
, который удовлетворяет системе ограничений ЗЛП, называется планом ЗЛП.
Определение. Набор чисел , который удовлетворяет не только системе ограничений ЗЛП, но и условиям неотрицательности, накладываемым на переменные, называется допустимым планомЗЛП.
Определение. Допустимый план 
, который доставляет экстремум линейной форме, называется оптимальным планом ЗЛП.
Представленные три формы постановок ЗЛП являются эквивалентными в том смысле, что после несложных преобразований можно перейти от одной к другой. Для этой цели необходимо уметь переходить от opt min к opt max и наоборот, от ограничений-неравенств к ограничениям-равенствам и наоборот.
Следующие два утверждения позволяют осуществлять переход от одной формы записи ЗЛП к другой.
Утверждение 1. Минимум линейной формы F равен максимуму линейной формы (–F), взятому с противоположным знаком, т. е.
Это утверждение достаточно просто доказать, построив график функции одной независимой переменной (см. рис. 1).
Рис. 1
Утверждение 2. Ограничение-неравенство исходной задачи вида «≤» преобразуется в ограничение-равенство добавлением к его левой части дополнительной (балансовой) неотрицательной переменной, а ограничение-неравенство вида «≥» преобразуется в ограничение-равенство вычитанием из его левой части дополнительной (балансовой) неотрицательной переменной.
|
неравенства вида 
соответствует вполне определенное решение 
равенства вида
|
И наоборот, каждому решению равенства (12) соответствует вполне определенное решение 
неравенства (11).
Доказательство. Пусть – некоторое решение неравенства (11), тогда вполне очевидно, что будет выполняться следующее неравенство
|
.
Обозначим разность между правой и левой частями неравенства (13) через an +1:
|
.
Соотношение (14) можно записать в виде
|
Из (15) следует, что совокупность чисел является решением уравнения (12).
Таким образом, прямая часть теоремы доказана, а обратная часть доказывается аналогично.
Пример 1. Привести к первой канонической форме ЗЛП
Задача сформулирована в общей постановке, так как для симметричной формы характерно наличие только ограничений типа «≤».
В первой канонической форме задача запишется следующим образом
Пример 2. Привести к первой канонической форме ЗЛП
Рис. 2 Рис. 3
Из рисунков 2, 3 видно, что для переменной х 1 выполняется условие неотрицательности.
Вместо переменной х 2 введем новые переменные 
и 
по формуле
|
С учетом (16) из исходной постановки ЗЛП можно исключить переменную х 2, и задача примет вид
Введя балансовые переменные х 5 ³ 0 и х 6 ³ 0, запишем задачу в первой канонической форме.
Поиск по сайту: