4768

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

Контрольная

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

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

Русский

2012-11-26

69 KB

96 чел.

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

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


 

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

22384. ОСНОВЫ ПРОЕКТИРОВАНИЯ ПРОМЫШЛЕННЫХ ЗДАНИЙ. ОБЪЕМНО-ПЛАНИРОВОЧНЫЕ И КОНСТРУКТИВНЫЕ РЕШЕНИЯ. ТИПИЗАЦИЯ СБОРНЫХ ЭЛЕМЕНТОВ 17.73 KB
  Так например элементы перекрытий и покрытий должны быть прочными и достаточно жесткими чтобы их прогиб не нарушал эксплуатационного режима здания: стены и колонны поддерживающие покрытия должны быть прочными и устойчивыми. Все здания в целом должны обладать пространственной жесткостью т. Здания бывают каркасными и бескаркасными. В бескаркасных зданиях пространственная жесткость создаётся благодаря совместной работе продольных и поперечных стен соединенных покрытиями в единую пространственную систему.
22385. СТАДИИ НАПРЯЖЕННО-ДЕФОРМИРОВАННОГО СОСТОЯНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ 360.47 KB
  2: стадия I до появления трещин в бетоне растянутой зоны когда напряжения в бетоне меньше временного сопротивления растяжению и растягивающие усилия воспринимаются арматурой и бетоном совместно; стадия II после появления трещин в бетоне растянутой зоны когда растягивающие усилия в местах где образовались трещины воспринимаются apматypoй и участком бетона над трещиной а на участках между трещинами арматурой и бетоном совместно; стадия III стадия разрушения характеризующаяся относительно коротким периодом работы элемента когда...
22386. МЕТОД РАСЧЕТА КОНСТРУКЦИЙ ПО ПРЕДЕЛЬНЫМ СОСТОЯНИЯМ. СУЩНОСТЬ МЕТОДА. ДВЕ ГРУППЫ ПРЕДЕЛЬНЫХ СОСТОЯНИЙ. КЛАССИФИКАЦИЯ НАГРУЗОК. ОСНОВНЫЕ ПОЛОЖЕНИЯ РАСЧЕТА 17.19 KB
  Конструкция может потерять необходимые эксплуатационные качества по одной из двух причин: 1 в результате исчерпания несущей способности разрушения материала в наиболее нагруженных сечениях потери устойчивости некоторых элементов или всей конструкции в целом; 2 вследствие чрезмерных деформаций прогибов колебаний осадок а также изза образования трещин или чрезмерного их раскрытия. Строительные конструкции рассчитывают по методу предельных состояний который дает возможность гарантировать сохранение...
22387. ИЗГИБАЕМЫЕ ЭЛЕМЕНТЫ. РАСЧЕТЫ ПРОЧНОСТИ ПО НОРМАЛЬНЫМ И НАКЛОННЫМ СЕЧЕНИЯМ ЭЛЕМЕНТОВ ПРЯМОУГОЛЬНОГО И ТАВРОВОГО ПРОФИЛЯ. РАСЧЕТ ПОПЕРЕЧНЫХ СТЕРЖНЕЙ 866.99 KB
  РАСЧЕТЫ ПРОЧНОСТИ ПО НОРМАЛЬНЫМ И НАКЛОННЫМ СЕЧЕНИЯМ ЭЛЕМЕНТОВ ПРЯМОУГОЛЬНОГО И ТАВРОВОГО ПРОФИЛЯ. Поперечные стержни сеток распределительная арматура принимают меньших диаметров общим сечением не менее 10 сечения рабочей арматуры поставленной в месте наибольшего изгибающего момента; располагают их с шагом 250 300 мм но не реже чем через 350 мм. Железобетонные балки могут иметь прямоугольные тавровые двутавровые трапецеидальные поперечные сечения рисунок 7.2 – Формы поперечного сечения балок и схемы их армирования а прямоугольная;б...
22388. Сжатые и растянутые элементы. Конструктивные особенности. Расчет прочности центрально И Внецентренно растянутых элементов. Расчет внецентренно сжатых элементов таврового и двутаврового сечений 1.23 MB
  Расчет прочности центрально И Внецентренно растянутых элементов. Расчет внецентренно сжатых элементов таврового и двутаврового сечений. НАПРЯЖЕННОЕ СОСТОЯНИЕ РАСТЯНУТЫХ И СЖАТЫХ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ Сжатые элементы. Конструктивные особенности сжатых элементов К центральносжатым элементам условно относят: промежуточные колонны в зданиях и сооружениях; верхние пояса ферм загруженных по узлам; восходящие раскосы и стойки ферменной решетки.
22389. ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. СОПРОТИВЛЕНИЕ ОБРАЗОВАНИЮ ТРЕЩИН ЦЕНТРАЛЬНО РАСТЯНУТЫХ, ИЗГИБАЕМЫХ, ВНЕЦЕНТРЕННО СЖАТЫХ И РАСТЯНУТЫХ ЭЛЕМЕНТОВ. ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ 101.52 KB
  ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. СОПРОТИВЛЕНИЕ ОБРАЗОВАНИЮ ТРЕЩИН ЦЕНТРАЛЬНО РАСТЯНУТЫХ ИЗГИБАЕМЫХ ВНЕЦЕНТРЕННО СЖАТЫХ И РАСТЯНУТЫХ ЭЛЕМЕНТОВ. ТРЕЩИНОСТОЙКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. Общие положения Трещиностойкость элементов как условлено ранее это сопротивление образованию трещин в стадии I или сопротивление раскрытию трещин в стадии II.
22390. РАСЧЕТ ПО ОБРАЗОВАНИЮ ТРЕЩИН, НОРМАЛЬНЫХ И НАКЛОННЫХ К ПРОДОЛЬНОЙ ОСИ ЭЛЕМЕНТА. СОПРОТИВЛЕНИЕ РАСКРЫТИЮ ТРЕЩИН. ОПРЕДЕЛЕНИЕ РАССТОЯНИЯ МЕЖДУ ТРЕЩИНАМИ 235.22 KB
  РАСЧЕТ ПО ОБРАЗОВАНИЮ ТРЕЩИН НОРМАЛЬНЫХ И НАКЛОННЫХ К ПРОДОЛЬНОЙ ОСИ ЭЛЕМЕНТА. СОПРОТИВЛЕНИЕ РАСКРЫТИЮ ТРЕЩИН. ОПРЕДЕЛЕНИЕ РАССТОЯНИЯ МЕЖДУ ТРЕЩИНАМИ. Расчет по образованию трещин нормальных к продольной оси элемента Этот расчет заключается в проверке условия что трещины в сечениях нормальных к продольной оси элемента не образуются если момент внешних сил М не превосходит момента внутренних усилий в сечении перед образованием трещин Мcrcт.
22391. КРИВИЗНА ОСИ ПРИ ИЗГИБЕ, ЖЕСТКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. ОБЩИЕ ПОЛОЖЕНИЯ РАСЧЕТА 161.5 KB
  КРИВИЗНА ОСИ ПРИ ИЗГИБЕ ЖЕСТКОСТЬ И ПЕРЕМЕЩЕНИЯ ЖЕЛЕЗОБЕТОННЫХ ЭЛЕМЕНТОВ. ОБЩИЕ ПОЛОЖЕНИЯ РАСЧЕТА Расчет перемещений железобетонных элементов прогибов и углов поворота связан с определением кривизны оси при изгибе или с определением жесткости элементов. Считается что элементы или участки элементов не имеют трещин в растянутой зоне если при действии постоянных длительных и кратковременных нагрузок с коэффициентом надежности по нагрузке γf= 1 трещины не образуются. Кривизна оси при изгибе и жесткость железобетонных элементов на участках...
22392. БЕТОН. СТРУКТУРА БЕТОНА. ПРОЧНОСТЬ И ДЕФОРМАТИВНОСТЬ. КЛАССЫ И МАРКИ БЕТОНА. АРМАТУРА. НАЗНАЧЕНИЕ И КЛАССИФИКАЦИЯ. МЕХАНИЧЕСКИЕ СВОЙСТВА. АРМАТУРНЫЕ СВАРНЫЕ ИЗДЕЛИЯ 130.03 KB
  СТРУКТУРА БЕТОНА. КЛАССЫ И МАРКИ БЕТОНА. В связи с этим в бетоне со временем прочность нарастает несколько изменяется объем в зависимости от соотношения состава бетона и химического состава цемента происходит усадка или при использовании специальных цементов расширение. По этим полостям и частично капиллярам возможно перемещение влаги и газа в толще бетона.