1. Система огранич-й представл. В канонич. Видет

О1. Огранич.ЗЛП имеет предпочтительный вид, если при неотрицат. правой части bi>=0, левая часть содержит переменные с коэф-ом 1 1кот.в др. ур-ях системы входят с коэф-ом.

О2. Переменная входящая в одно из ур-ий системы с коэф-ом 1, а в ост. С коэф-ом 0, наз-ся предпочтительной переменной.

О3. Сист.ур-ий имеет препочтит-ый вид, если каждое ее ур-ие имеет предпочтит. вид.

2. Пусть система огр-ий злп представлена в виде:

bi>=0,xj>=0(j=1,m),

(i=1,m).

Приведем систему огранич. К канонич. Виду, для этого в каждое нер-во добавим новые неотрицат. переменные:

bi>=0,xy>=0(j=1,n+m) (i=1,m).

Xn+1,Xn+2,…,Xn+m-явл-ся предпочтительными и тогда случай 2 св-ся к случаю 1.

3. Пусть система ограничений злп представлена в виде

Система имеет канонич-й вид однако в ней отсутствуют переменные являющ-ся предпочтительными.Тогда в этом случае говорят что есть необх-ть решить М-задачу. Для того чтобы построить М-задачу необходимо прибавить к каждому ур-ю системы новые искусственные переменные и их будем обозначать(у1,у2,…,уm).Тогда система огранич. Будет иметь вид: Новые переменные наз-ся искусств. Базисом, все переменные его неотрицат-ые. Если ЗЛП на макс. То коэф-т со знаком –М, если залача на миним. То +М и тогда

ЦФ имеет вид

Переменные уi явл-ся предпочтительными и случай 3 св-ся к случаю 1.

4. Пусть система огранич. ЗЛП представлена виде нер-в

52. Элементы теории двойственности. Прямая и двойственная задачи линейного программирования. Основные теоремы двойственности. Применение двойственного симплексного метода.

В каждой задаче лин.прогр-ия существует другая двойственная или сопряженная ей задача. Теория двойственности оказалась полезной для проведения качеств. исследований в обл. ТО.

Прямая и двойственная ЗЛП.Основное содержание плановой экономической работы на предприятии составл. реш-ие задачи достижение наилучшего экономич. эффекта при огранич.ресурсах; математически св-ся к ЗЛП и м/б решена известными методами. Причем план выпуска новой продукции оказ-ся тесно связан с так называемой системой цен (системой оценок) прим-х к ресурсам (отходы основн.произ-ва), пусть на некот. предприятии решено использ отходы основн. произв-ва , для этого намеч-ся наладить выпуск изделий широкого потребления. Известно, что сбыт новой продукции обеспечен, при этом кол-во исх-х материалов сырья ограничено. Ставится задача, достичь наибольшей прибыли от произв-ва.

Зная прямую задачу всегда можно построить двойств.и наоборот.

Прямая. Необходимо найти такой план произв-ва х1,х2,…,хn удовлетв.сисетеме огранич. Х=(х1,х2,…,хn)

xi>=0(i=1,n). Для кот.

Тогда двойственная или сопряж. задача будет сформулирована след.образом. Необходимо найти такую систему оценок У=(у1у2...уm).

Основная теорема двойственности.

Т.1. Для любых допустимых решений Х=(х1х2...хn) и У=(у1у2…уm) пары двойственных задач справедливо нер-во:

-основное нер-во теории двойств-ти.

Экономич-ое содерңание этого нер-ва закл-ся в том, что обәая стоим-ть всего произведенного продукта не больше суммарной оценки ресурса.

Т.2.(т. О минимаксе необход. Признак оптим-ти доп-х реш-ий).

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

Zmax=Tmin

Т.3. Достаточный признак сущ-ия оптимального реш-я, если Х и У доп-ые реш-ия пары двойств-х задач, для кот вып-ся рав-во Zmax=Tmin

То Х есть оптим-ое реш-е прямой задачи, У есть оптим. Реш-е двойственности.

Т.4. Для того чтобы реш-е Х явилось оптим. реш-м пары двойств-х задач необходимо и достаточно чтобы выполнялось след. Усл-е: