4768

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

Контрольная

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

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

Русский

2012-11-26

69 KB

99 чел.

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

Для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов 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


 

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

46147. Бизнес-план. Компьютерный клуб «Chicago» 337.5 KB
  В случае стабильного получения запланированной прибыли уже через несколько лет он будет иметь возможность открыть свои филиалы в любом районом центре Актюбинской области. Как давно вы увлекаетесь компьютерными играми меньше года от 1 до 3 лет более 3х лет 11. Ваш возраст от 6 до 16 лет от 16 до 25 лет от 25 и старше В анкетировании приняло участи 50 человек. Результаты анкетирования 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 нет от 3 до 5 высокий уровень до 2 часов с 14 до 19 от 10 до 30 минут просто поиграть ction развлечение меньше...
46148. Учебник «Гидрология и гидротехнические сооружения» 2.96 MB
  Последние десятилетия характеризуются интенсивным развитием промышленности и сельского хозяйства ростом городов и населенных пунктов что повлекло за собой резкое увеличение потребления воды с ее забором из различных поверхностных природных источников: морей рек водохранилищ и озер а также из подземных источников. 16 км3 воды в 20 .25 раза больше воды требуется атомной электростанции. км3 воды.
46150. Первые математические теории в Древней Греции 212.45 KB
  В это время ученые пришли к мысли к которой возвращались затем не раз что математика является универсальным языком для выражения законов природы что все есть число. Проходит немного времени и начинается исследование законов самой логики что находит блестящее завершение в системе Аристотеля. В этой школе впервые была высказана гипотеза что земля имеет форму цилиндра и весит посередине вселенной Анаксиманур. Ионийцы...
46151. Особливості застосування заходів процесуального примусу 669.17 KB
  Виявити риси схожості та відмінності окремих заходів процесуального примусу а також співвідношення їх з кримінальноправовими санкціями їх роль та місце в правовій системі України зокрема в системі Кримінального процесу України Зробити відповідні висновки. 47 КК України. 47 КК України. Запобіжне обмеження тобто заборона особі щодо якої порушено кримінальну справу виїжджати за межі України до закінчення досудового слідства чи судового розгляду ст.
46152. Технология производства земляных и бетонных работ 964 KB
  Тип грунта супесь с примесью щебня 30. Земляным сооружением называется инженерное сооружение устраиваемое из грунта в грунтовом массиве или возводимое на поверхности земли. При строительстве ведется переработка грунта с целью подготовки основания под здания устройства дорог. К основным процессам переработки грунта можно отнести: разработку перемещение и укладку его.
46153. Основы организации работы по ведению бухгалтерского учета в кредитных организациях 200.79 KB
  Введение В процессе становления рыночной экономики когда банки действуют в условиях жесткой конкуренции и нестабильной экономической ситуации бухгалтерский учет не сводится только к отражению операций банка. Основная роль его состоит в использовании бухгалтерской информации для планирования активных и пассивных операций банка. Бухгалтерский учет в банке дает возможность ответа на вопросы о состоянии и движении имущества банка денежных средств кредитов фондов о расходах и доходах финансовых результатах деятельности банка.
46154. Создание поверхности для защиты от коррозии внутренних и внешних поверхностей труб тепловых и водопроводных систем 5.53 MB
  Сбор нагрузок на колонны. Колонны предназначены для поддержания железобетонного перекрытия.396 Этажи От перекрытия и покрытия Собственный вес колонны Расчетная суммарная нагрузка Длительная Кратковременная NДЛ NКР NПОЛН 4 1 1171 1223 Расчет нагрузки колонны Подсчет расчетной нагрузки на колонну. Расчет колонны первого этажа N=3504кН; ℓ 01=2.
46155. Оценка эффективности предпринимательской деятельности ОАО «Газпром» 208 KB
  Анализ эффективности деятельности предприятия ОАО Газпром 8 2. Для повышения деловой и инвестиционной активности предприятия все более актуальна необходимость более эффективного управления ими на основе комплексной достаточно полной и объективной системы оценок их финансовохозяйственной деятельности в сложной экономической обстановке рыночных изменений в условиях динамичной внешней среды. Анализ финансовохозяйственной деятельности служит базой для принятия управленческих решений переоценить его значение для эффективного функционирования...