4768

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

Контрольная

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

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

Русский

2012-11-26

69 KB

94 чел.

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

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


 

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

69677. ІНСТРУКЦІЯ SWITCH-CASE (КОНСТРУКЦІЯ ВИБОРУ) 52 KB
  Нами залишилася непоміченій дуже важлива конструкція — switch-case. Дана конструкція призначена для вибору дій, залежно від значення вказаного виразу. Конструкція switch-case чимось нагадує оператора if-else, який, по суті, є її аналогом.
69678. ОБРОБКА ПОМИЛОК 24 KB
  Інтерпретатор PHP дозволяє програмістові визначити, які повідомлення про помилки потрібно виводити, а які — ні. Поки ви відладжуєте програму, я рекомендую виводити всі повідомлення про помилки і всі попередження, а потім, коли програма нормально працює, виводити тільки повідомлення про помилки.
69679. ГІПЕРТЕКСТОВІ ПОСИЛАННЯ 119 KB
  Гіпертекстове посилання складається з двох частин: вказівника і адресної частини (URL). Вказівник - текст (або графічне зображення), на якому користувач повинен клацнути для того, щоб перейти в інше місце. URL - вказує адресу, з якої броузер буде завантажувати документ...
69680. ТЕГ TEXTAREA 113 KB
  Ми переходимо до розгляду багаторядкового поля введення. У HTML ця можливість реалізується за допомогою тега TEXTAREA. Поле, що створюється цим тегом, дозволяє вводити і відправляти не один рядок, а відразу декілька.
69681. Графіка Web-сторінок 101.5 KB
  Графіка Web-сторінок може містити як прості зображення, так і складні. Важливим у використанні графіки є не міра її складності, а ефективність у питаннях передавання тієї інформації, яку необхідно надати користувачам.