4768

Метод искусственного базиса. Понятие двойственной задачи линейного программирования

Контрольная

Информатика, кибернетика и программирование

Метод искусственного базиса М -задача. Для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов Pj не всегда есть m единичных. Рассмотрим такую задачу. Пусть требуется найти максимум...

Русский

2012-11-26

69 KB

98 чел.

Метод искусственного базиса (М-задача).

Для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов Pj не всегда есть m единичных.

Рассмотрим такую задачу:

Пусть требуется найти максимум функции

F = c1x1 + c2x2 + ……+ cnxn    (1)

при условиях

………………………………………     (2)

где bi  0 (i=l, m), m<.n и среди векторов P1, P2, …, Pn нет m единичных.

Определение. Задача, состоящая в определении максимального значения функции

F = c1x1 + c2x2 + ……+ cnxn xn+1- …- Мxn+m   (3)

при условиях

………………………………………      (4)

где M — некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей (М-задачей) по отношению к задаче (1) — (2).

Расширенная задача имеет опорный план

Х=(0; 0; ...; 0; b1; b2; ...;bm).

определяемых системой единичных векторов Pn+1; Рп+2, … Рп+т, образующих базис m-ro векторного пространства, который называется искусственным. Сами векторы, так же как и переменные xn+i (i=l, m), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Теорема Если в оптимальном плане X*=(x*1, x*2, ...; x*n, x*n+1; ...; x*n+m) расширенной задачи (3) — (4) значения искусственных переменных x*n+i=0 (i=1, m), то X*=(x*1, x*2, ...; x*n) является оптимальным планом задачи (1) — (2).

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

Значения индексной строки ∆0, ∆1, …, ∆n состоят из двух частей, одна из которых зависит от M, а другая — нет. Заполняют симплекс - таблицу, которая содержит на одну строку больше, чем обычная симплексная таблица. При этом в (m+2)-ю строку помещают коэффициенты при M, а в (m+1)-ю – слагаемые, не содержащие M. При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m+2)-й строки. Искусственный вектор, исключенный из базиса, в следующую симплекс-таблицу не записывают. Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

Итерационный процесс по (m+2) -и строке ведут до тех пор, пока:

  1.  либо все искусственные векторы не будут исключены из базиса;
  2.  либо не все искусственные векторы исключены, но (m+2)-я строка не содержит больше отрицательных элементов в индексах ∆1, …, ∆n.

В первом случае базис отвечает некоторому опорному плану исходной задачи и определение ее оптимального плана продолжают по (m+1)-й строке.

Во втором случае, если значение ∆0 отрицательное, исходная задача не имеет решения; если же ∆0=0, то найденный опорный план исходной задачи является вырожденным и базис содержит по крайней мере один из векторов искусственного базиса.

Этапы нахождения решения задачи (1) — (2)

методом искусственного базиса:

  1.  Составляют расширенную задачу (3) — (4).
  2.  Находят опорный план расширенной задачи.
  3.  С помощью обычных вычислений симплекс-метода исключают искусственные переменные из базиса. В результате либо находят опорный план исходной задачи (1) — (2), либо устанавливают ее неразрешимость.
  4.  Используя найденный опорный план задачи (1) — (2), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

Пример. 

Найти минимум функции F= - 2x1 + 3x2 - 6x3 - x4

при ограничениях:

2x1+x2-2x3+x4=24

x1+2x2+4x3≤22

x1-x2+2x3≥10

xi≥0, i=1,4

Решение.

Запишем данную задачу в форме основной задачи: найти максимум функции F=  2x1 - 3x2 + 6x3 + x4

при ограничениях:

2x1+x2-2x3+x4=24

x1+2x2+4x3+x5=22

x1-x2+2x3- x6=10

xi≥0, i=1, 6

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

Среди векторов P1, Р2,P6 только два единичных (P4 и P5). Поэтому в левую часть третьего уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную х7 и рассмотрим расширенную задачу, состоящую в максимизации функции

F=  2x1 - 3x2 + 6x3 + x4 - Мх7

при ограничениях:

2x1+x2-2x3+x4=24

x1+2x2+4x3+x5=22

x1-x2+2x3- x6 +x7=10

Расширенная задача имеет опорный план Х=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P4, P5, Р7.

Понятие двойственной (соапряженной) задачи линейного программирования.

Правила построения двойственной задачи.

С каждой задачей линейного программирования (ЗЛП), которая называется двойственной задачей (или сопряженной) по отношению к исходной задаче, которая называется прямой.

Двойственная задача строится по отношению к прямой задаче, записанной в стандартной форме:

F=c1x1+c2x2+…+cnxn       max    (3.6)

a11x1+a12x2+…+a1nxn ≤ b1,

a21x1+a22x2+…+a2nxn ≤ b2,

………………………………

ak1x1+ak2x2+…+aknxn ≤ =bk,     (3.7)

ak+1,1x1+ak+1,2x2+…+ak+1,nxn=bk+1,

………………………………

am1x1+am2x2+…+amnxn=bm,

xj ≥ 0, , l ≤ n    (3.8)

Задача, состоящая в нахождении минимального значения функции

   

L = b1y1 + b2y2 + … + bmym         (3.9)   

при условиях

 a11y1 + a12y2 +…+ am1ym  ≥ c1

a21y1 + a22y2 +…+ am2ym ≥ c2 

………………………………

a1ly1 + a2ly2 +…+ amlym  ≥ cl     (3.10)

al+1,1y1 + al+1,2y2 +…+ al+1,mym = cl+1 

………………………………

am1y1 + am2y2 +…+ amnym = cm

yi ≥ 0,    ,    k ≤ m    (3.11)

называется двойственной по отношению к задаче (3.6) – (3.8).

Правила построения двойственной задачи приведены в таблице:


Структурные характ
еристики ЗЛП

Задача линейного программирования

Прямая

Двойственная

1. Целевая функция

Максимизация (max)

Минимизация (min)

2. Количество переменных

n переменных

Равно количеству ограничений прямой задачи (3.7),  yi,  т.е. m

3. Количество ограничений

m ограничений

Равно количеству переменных прямой задачи xj, , т.е n

4. Матрица коэффициентов в системе ограничений

5. Коэффициенты при переменных в целевой функции

c1,c2,…,cn      

b1,b2,…,bm

6. Правая часть системы ограничений

b1,b2,…,bm

c1,c2,…,cn      

7. Знаки в системе ограничений

а) xj ≥ 0- условие неотрицательности

j-е ограничение имеет знак «≥»

б) на переменную  xj  не наложено условие неотрицательности

j-е ограничение имеет знак «=»

в) i-е ограничение имеет знак «≤»

переменная  yi≥0

г)  i-е ограничение имеет знак «=»

на переменную  yi   не наложено условие неотрицательности

Примечание

  1.  Прямая задача на максимум и двойственная на минимум являются взаимодвойственными задачами. Поэтому можно считать задачу (3.9) – (3.11) прямой ЗЛП , а задачу (3.6) – (3.8) – двойственной к ней задачей. При этом правила построения двойственной ЗЛП сохраняются, лишь с тем изменением, что исходной считается задача на минимум.
  2.  Если исходная задача решается на  max (min), а в системе ограничений ) i-е (j-е) ограничение имеет знак «≤» («≥»), то для построения двойственной задачи необходимо:

а) либо домножить обе части  i-го (j-го) неравенства на (-1) и поменять знак на «≤» («≥»)

б) либо привести  i-е (j-е) ограничение к равенству путем введения дополнительной переменной xn+i≥0


 

А также другие работы, которые могут Вас заинтересовать

41442. КИСЛОТИ, ОСНОВИ, ЇХ КЛАСИФІКАЦІЯ, ОДЕРЖАННЯ І ВЛАСТИВОСТІ 567 KB
  Дo бiнpниx cпoлyк нлeжть oкcиди глoгeнiди нiтpиди кpбiди гiдpиди тoщo дo тpинpниx HNOз NOH тoщo. Hйвжливiшими клcми нeopгнiчниx cпoлyк з фyнкцioнльними oзнкми є oкcиди киcлoти ocнoви мфoтepнi гiдpoкcиди coлi. З xiмiчними влcтивocтями oкcиди пoдiляють н coлeтвopнi i нecoлeтвopнi. Coлemвopнi цe ткi oкcиди якi в pзi пepeбiгy пeвниx xiмiчниx peкцiй здтнi yтвopювти coлi.
41443. СОЛІ, ВИДИ СОЛЕЙ, ВЛАСТИВОСТІ, НОМЕНКЛАТУРА 1.66 MB
  Coлi мoжн poзглядти як пpoдyкти пoвнoгo бo чcткoвoro змiщeння томiв Гiдpoгeнy y киcлoтx н тoми мeтлiв бo як пpoдyкти пoвнoгo чи чcткoвoгo змiщeння гiдpoкcильниx гpyп в ocнoвx н киcлoтнi злишки. 3 тoчки зopy тeopiї eлeктpoлiтичнoї диcoцiцiї coлi цe peчoвини якi пiд чc диcoцiцiї poзпдютьcя н ктioни мeтлiв т нioни киcлoтниx злишкiв: N3PO4  3N PO43 Poзpiзняють ткi типи coлeй: нopмльнi бo cepeднi киcлi ocновнi пoдвiйнi змiшнi т кoмплeкcнi. Hopмльнi coлi цe пpoдyкти пoвнoгo змiщeння томiв Гiдpoгeнy н тoми мeтлy в мoлeкyлx киcлoт...
41444. ХІМІЧНА РІВНОВАГА ТА УМОВИ ЇЇ ЗМІЩЕННЯ 630 KB
  Xiмiчн кiнeтик вивчє як гoмoгeннi тк i reтepoгeннi peкцiї. Гoмoгeннuмu нзивютьcя peкцiї щo вiдбyвютьcя в oднopiднoмy cepeдoвищi гoмoгeннiй cиcтeмi нпpиклд в гзoпoдiбнiй cyмiшi бo в piдкoмy poзчинi. Гemepoгeнними нзивютьcя peкцiї щo вiдбyвютьcя в нeoднopiднoмy cepeдoвищi гeтepoгeннiй cиcтeмi мiж peчoвинми якi пepeбyвють y piзниx фзx твepдiй i piдкiй гзoпoдiбнiй i piдкiй тoщo. У згльнoмy poзyмiннi швидкicть peкцiї вiдпoвiдє чиcлy eлeмeнтpниx ктiв взємoдiї щo вiдбyвютьcя з oдиницю чcy: для гoмoгeнниx peкцiй в oдиницi oб'ємy дпя...
41445. POЗЧИHИ. XAPAKTEPИCTИKA POЗЧИHIB TA CПOCOБИ BИPAЖEHHЯ ЇXHЬOГO CKЛAДУ 367.5 KB
  Poзчин cклдєтьcя з poзчинeниx peчoвин i poзчинник тoбто cepeдoвищ в якoмy цi peчoвини piвнoмipнo poзпoдiлeнi y виглядi мoлeкyл бo йoнiв. Якщo ж poзчин yтвopюєтьcя внcлiдoк змiшyвння гзy з гзoм piдини з piдинoю твepдoї peчoвини з твepдoю poзчинникoм ввжють кoмпoнeнт кiлькicть якoгo пepeвжє. Пpoцec пepexoдy peчoвини якy poзчиняють y тoвщу poзчинник нзивєтьcя poзчuнeнням. Цi явищ ткoж дeякi iншi вкзyють н xiмiчнy взємoдiю poзчинeнoї peчoвини з poзчинникoм.
41446. ДИСОЦІАЦІЯ КИСЛОТ ОСНОВ ТА СОЛЕЙ 932.5 KB
  Основні положенн тeopiї eлeктpoлiтичрoї диcoцiцiї. Cтупiнь eлeктpoлітичнoї диcoцiцiї.Основні положенн тeopiї eлeктpoлiтичнoї диcoцiцiї. Cтупiнь eлeктpoлітичнoї диcoцiцiї.
41447. Суть гідролізу, його види. Складання рівнянь гідролізу різних солей 476.5 KB
  Суть гідролізу його види.Складання рівнянь гідролізу різних солей.Суть гідролізуйого види. Як показано в прикладі розчин став лужним внаслідок гідролізу солі СНзСООNа.
41448. OKИCHO-BIДHOBHI PEAKЦIЇ 764.5 KB
  З змiнoю cтyпeня oкиcнeння eлeмeнтiв якi вxoдять дo cклдy виxiдниx peчoвин т пpoдyктiв peкцiї xiмiчнi peкцiї мoжн пoдiлити н двi гpyпи. Цe peкцiї: пoдвiйнoгo oбмiнy бo витicнeння кoмплeкcoyтвopeння дeякi peкцiї poзклдy peкцiї iзoмepизцiї пoлiмepизцiї coцiцiї тoщo: Дo дpyгoї гpyпи нлeжть peкцiї щo вiдбyвютьcя iз змiнoю cтyпeнiв oкиcнeння eлeмeнтiв peгyючиx peчoвин т пpoдyктiв peкцiї. Tкi peкцiї нзивютьcя oкucнoвiднoвнuмu нпpиклд: У пpoцeci цiєї peкцiї cтyпiнь oкиcнeння Цинкy змiнюєтьcя вiд 0 дo 2 Гiдpoгeнy вiд 1 дo 0....
41449. EЛEKTPOЛIЗ, ЙОГО СУТЬ ТА ЗНАЧЕННЯ 1012 KB
  Суть електролізу Особливості електролізу розплавів та розчинів. Практичне значення електролізу. Суть електролізу Особливості електролізу розплавів та розчинів. : Закони електролізу вперше були сформульовані видатним англійським фізиком М.
41450. ВЛАСТИВОСТІ ГАЛОГЕНІВ. ВОДНЕВІ СПОЛУКИ ГАЛОГЕНІВ 851.5 KB
  Добування і властивості хлору. На відміну від Хлору Брому Йоду й Астату Флуор в усіх своїх сполуках виявляє ступінь окиснення тільки З електронних структур видно що в атомах Хлору Брому Йоду й Астату в зовнішньому електронному шарі є вакантні dорбіталі. πЗв'язок помітно зміцнює молекулу і тому енергія дисоціації молекули хлору СІ2 239кДж моль значно більша ніж молекули фтору F2 1588 кДж моль.