АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Канонические формы постановки ЗЛП

Читайте также:
  1. B) Количественная определенность относительной формы стоимости
  2. I. Виды и формы СРС по учебной дисциплине
  3. II. Создание многотабличной пользовательской формы.
  4. IV. Формы контроля за исполнением Административного регламента
  5. QNET комментирует создание платформы электронной коммерции Globby в Сингапуре
  6. Supinum. Perfectum indicativi passivi. Четыре основные формы глагола
  7. VI. Принятые формы сексуальных отношений
  8. VI. ФОРМЫ ОРГАНИЗАЦИИ И КОНТРОЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ
  9. А) Причины незавершенности реформы
  10. А32. Социальные движения в Греции в эллинистическое время. Реформы Агиса и Клеомена в Спарте.
  11. Аграрный вопрос в России в ХХв. Реформы Столыпина.
  12. Аккумулятивные и абразионные формы рельефа побережья.

ЗЛП, заданной в канонической форме, называется задача, в которой необходимо найти оптимум линейной формы

(8)

при ограничениях–равенствах:

(9)

(10)

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

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

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

Определение. Допустимый план , который доставляет экстремум линейной форме, называется оптимальным планом ЗЛП.

Представленные три формы постановок ЗЛП являются эквивалентными в том смысле, что после несложных преобразований можно перейти от одной к другой. Для этой цели необходимо уметь переходить от opt min к opt max и наоборот, от ограничений-неравенств к ограничениям-равенствам и наоборот.

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

Утверждение 1. Минимум линейной формы F равен максимуму линейной формы (–F), взятому с противоположным знаком, т. е.


Это утверждение достаточно просто доказать, построив график функции одной независимой переменной (см. рис. 1).

 

 

 

Рис. 1

 

Утверждение 2. Ограничение-неравенство исходной задачи вида «≤» преобразуется в ограничение-равенство добавлением к его левой части дополнительной (балансовой) неотрицательной переменной, а ограничение-неравенство вида «≥» преобразуется в ограничение-равенство вычитанием из его левой части дополнительной (балансовой) неотрицательной переменной.

(11)
Теорема. Всякому решению неравенства вида соответствует вполне определенное решение равенства вида

(12)

И наоборот, каждому решению равенства (12) соответствует вполне определенное решение неравенства (11).

Доказательство. Пусть – некоторое решение неравенства (11), тогда вполне очевидно, что будет выполняться следующее неравенство

(13)
.

Обозначим разность между правой и левой частями неравенства (13) через an +1:


(14)
.

Соотношение (14) можно записать в виде

(15)

Из (15) следует, что совокупность чисел является решением уравнения (12).

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

Пример 1. Привести к первой канонической форме ЗЛП

Задача сформулирована в общей постановке, так как для симметричной формы характерно наличие только ограничений типа «≤».

В первой канонической форме задача запишется следующим образом

Пример 2. Привести к первой канонической форме ЗЛП

Рис. 2 Рис. 3

Из рисунков 2, 3 видно, что для переменной х 1 выполняется условие неотрицательности.


 

Вместо переменной х 2 введем новые переменные и по формуле

(16)

С учетом (16) из исходной постановки ЗЛП можно исключить переменную х 2, и задача примет вид

Введя балансовые переменные х 5 ³ 0 и х 6 ³ 0, запишем задачу в первой канонической форме.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)