Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности

Название: Двойственный симплекс-метод и доказательство теоремы двойственности
Раздел: Рефераты по математике
Тип: реферат Добавлен 20:54:58 11 июля 2005 Похожие работы
Просмотров: 1993 Комментариев: 5 Оценило: 5 человек Средний балл: 2.8 Оценка: неизвестно     Скачать

ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Кафедра математики

КУРСОВАЯ

на тему:

Двойственный симплекс-метод и доказательство теоремы двойственности.

Студент группы МЭК 1-1 - А.С. Кормаков

Научный руководитель - Солодовников А.С.

МОСКВА – 2001

Содержание

1. Двойственность в линейном программировании.................................... 3

2. Несимметричные двойственные задачи. Теорема двойственности... 4

3. Симметричные двойственные задачи........................................................ 9

4. Виды математических моделей двойственных задач........................... 11

5. Двойственный симплексный метод........................................................... 12

6. Список используемой литературы............................................................ 14

1. Двойственность в линейном программировании

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

Связь исходной и двойственной задач состоит в том, что коэффици­енты Cj функции цели исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены B i систе­мы ограничений исходной задачи служаткоэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограни­чений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двой­ственной задачи может быть получено из решения исходной и наоборот.

В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ..., m ) единиц, из которых производится n видов продукций. Для производ­ства 1 ед. i -й продукции расходуется aij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, ..., n) количество ед. j -й продукций, Тогда исходную задачу сформулируем так.

Найти вектор Х =(x1 , x2 , …, xn ), который удовлетворяет ограни­чениям

a11 x1 + a12 x2 + … + a1n xn £ b1,

a21 x1 + a22 x2 + … + a2n xn £ b2, xj ³ 0 (j =1,2, ..., n)

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

am1 x1 + am2 x2 + … + amn xn £ bm,

и доставляет максимальное значение линейной функции

Z = C1 x1 + C2 x2 + … + Cn xn ,

Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через у i (j =1,2, ..., m) стоимость единицы i- горесурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j -й продукции, равна . Стоимость затрачен­ных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ³Cj , j =1,2, ..., n . Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом.

Найти вектор Y =(y1 , y2 , …, yn ), который удовлетворяет ограни­чениям

a11 y1 + a12 y2 + … + am1 ym £ C1,

a12 y1 + a22 y2 + … + am2 ym £ C2, yj ³ 0 (i =1,2, ..., m)

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

a1n y1 + a2n y2 + … + amn ym £ Cm,

и доставляет минимальное значение линейной функции

f = b1 y1 + b2 y2 + … + bm ym .

Рассмотренные исходная и двойственная задачи могут быть эко­номически интерпретированы следующим образом.

Исходная задача. Сколько и. какой продукции xj (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача. Какова должна быть цена еди­ницы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C i минимизироватьобщую стоимость затрат?

Переменные у i называются оценками или учетными, неявными ценами.

Многие задачи линейного программирования первоначально ста­вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

2. Несимметричные двойственные задачи. Теорема двойственности.

В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде нера­венств, причем в последней переменные могутбыть и отрицательными.Для простоты доказательств постановку задачи условимсязаписывать в матричной форме.

Исходная задача. Найти матрицу-столбец X = (x1 , x2 , …, xn ), которая удовлетворяет ограничениям

(1.1) AX = A0 , Х ³0

и минимизирует линейную функцию Z = СХ .

Двойственная задача. Найти матрицу-строку Y = (y1 , y2 , …, ym ), которая удовлетворяет ограничениям

(1.2) YA £ С

и максимизирует линейную функцию f = YA0

В обеих задачах C = (c1 , c2 , …, cn ) - матрица-строка, A0 = (b1 , b2 , …, bm ) — матрица-столбец, А = (aij ) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двой­ственных задач устанавливает следующая теорема.

Теорема (теорема двойственности). Если из пары двойствен­ных задач одна обладает оптимальным планом, то и другая имеет ре­шение, причем для экстремальных значений линейных функций выпол­няется соотношение

min Z = max f.

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

Д о к а з а т е л ь с т в о. Предположим, что исходная задача об­ладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис со­стоит из т первых векторов A 1 , A 2 , ..., A m . Тогда последняя симплекс­ная таблица имеет вид табл. 1.1.

Т а б л и ц а 1.1

i Базис С базиса A0 C1 C2 Cm Cm+1 cn
A1 A2 Am Am+1 An

1

2

.

.

.

m

A1

A2

.

.

.

Am

C1

C2

.

.

.

Cm

x1

x2

.

.

.

xm

1

0

.

.

.

0

0

1

.

.

.

0

...

...

.

.

.

.

0

0

.

.

.

1

x1, m+1

x2, m+1

.

.

.

xm, m+1

.

.

.

x1n

x2n

.

.

.

xmn

m+1 Zi - Cj Z0 Z1 – C1 Z2 – C2 ... Zm – Cm Zm+1 – Cm+1 Zn – Cn

Пусть D — матрица, составленная из компонент векторов оконча­тельного базиса A 1 , A 2 , ..., A m ; тогда табл. 1.1 состоит из коэффици­ентов разложения векторов A 1 , A 2 , ..., A n исходной системы по векто­рам базиса, т. е. каждому вектору A j в этой таблице соответствует та­кой вектор X j что

(1.3) Aj = DXj (j= 1,2, ,.., n).

Для оптимального плана получаем

(1.4) A 0 =DX* ,

где X* = ( x * 1 , x * 2 , …, x * m ) .

Обозначим через матрицу, составленную из коэффициентов раз­ложения векторов А j (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:

(1.5) A =D , D-1 A = ,

(1.6) A 0 =DX*; D -1 A 0 = X* ,

(1.7) min Z = C*X* ,

(1.8) = C* —C £ 0,

где С * = (C* 1 , C* 2 , …, C* m ),С = (C1 , C2 , …, Cm , Cm+1 , …, Cn ), a = (C*X 1 – C1 ; С*Х 2 - С2 , ..., C*X n – Cn ) = (Z1 –С1 ; Z2 - C2 ; ..., Zn — Cn ) — вектор, компоненты которого неположительны, так как они совпадают с ZjCj £ 0, соответствующими оптимальному плану.

Оптимальный план исходной задачи имеет вид X* =D-1 А 0 , поэтому оптимальный план двойственной задачи ищем в виде

(1.9) Y* = C*D -1 .

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA — С £ 0 , в левую часть которого подставим Y* . Тогда на основании (1.9), (1.5) и (1.8) получим

Y * А С = С* D -1 А С = С* - С £ 0,

откуда находим Y*A £ С.

Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двой­ственной задачи f (Y *) = Y*A 0 . Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) f (Y *) = Y*A 0 = C*D-1 A0 =C*X*=minZ(X ).

Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи.

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA 0 = f ( Y) , YAX £СХ = Z (X) , отсюда следует, что для любых планов Х и Y выполняется неравенство

(1.11) f ( Y) £ Z (X).

Этим же соотношением связаны и экстремальные значения max f ( Y) £min Z (Х) .Из последнего неравенства заключаем, что максималь­ное значение линейной функции достигается только в случае, еслиmax f (Y) = min Z (X), но это значение [см. (1.10)]f ( Y) достигает при плане Y* , следовательно, план Y* — оптимальный план двойственнойзадачи.

Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотно­шение max f (Y) = min Z (X).

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следу­ет, что f (Y ) £ -¥ . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Аналогично предположим, что линейная функция двойственной за­дачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X) ³ +¥. Это выражение также лишено смысла, поэтому исходная задача не име­ет решений.

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

Исходная задача. Найти минимальное значение линейной функ­ции Z = x2 – x4 – 3x5 при ограничениях

x1 + 2x2 - x4 + x5 = 1,

- 4x2 + x3 + 2x4 – x5 = 2, xij ³ 0 (j = 1, 2, …, 6)

3x2 + x5 + x6 = 5,

Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец

1 1 2 0 -1 1 0

A0 = 2 A = 0 -4 1 2 -1 0

3 0 3 0 0 1 1

1 0 0

2 -4 3

A ’’ = 0 1 0

-1 2 0

1 -1 0

0 0 1

Двойственная задача. Найти максимальное значение линейной функции f = y1 + 2y2 +5y3 при ограничениях

y1 £ 0,

2y1 – 4y2 + 3y3 £ 1,

y2 £ 0,

-y1 + 2y2 £ -1,

y1 – y2 + y3 £ -3,

y3 £ 0.

Решение исходной задачи находим симплексным методом (табл. 1.2).

i Базис С базиса A0 0 1 0 -1 -3 0
A1 A2 A3 A4 A5 A6

1

2

3

A1

A3

A6

0

0

0

1

2

5

1

0

0

2

-4

3

0

1

0

-1

2

0

1

-1

1

0

0

1

m + 1 Zi - Cj 0 0 -1 0 1 3 0

1

2

3

A5

A3

A6

-3

0

0

1

3

4

1

1

-1

2

-2

1

0

1

0

-1

1

1

1

0

0

0

0

1

m + 1 Zi - Cj -3 -3 -7 0 4 0 0

1

2

3

A5

A4

A6

-3

-1

0

4

3

1

2

1

-2

0

-2

3

1

1

-1

0

1

0

1

0

0

0

0

1

m + 1 Zi - Cj -15 -7 1 -4 0 0 0

1

2

3

A5

A4

A2

-3

-1

1

4

11/3

1/3

3

-1/3

-2/3

0

0

1

1

1/3

-1/3

0

1

0

1

0

0

0

2/3

1/3

m + 1 Zi - Cj -46/3 -19/3 0 -11/3 0 0 -1/3

Оптимальный план исходной задачи X* =(0; 1/3; 0; 11/3; 4; 0), при котором Zmin = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственнойзадачи. Согласно теореме двойственности оптимальный план двойствен­ной задачи находится из соотношения Y* = C*D -1 , где матрица D -1 - матрица, обратная матрице, составленной из компонент векторов, вхо­дящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A5 , A4 , A2 ; значит,

1 -1 2

D = ( A5 , A4 , A2 ) = -1 2 -4

1 0 3

Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах A1 , A3 , A6 четвертой итерации:

2 1 0

D-1 = -1/3 1/3 2/3

-2/3 -1/3 1/3

Из этой же итерации следует С* = (— 3; —1; 1). Таким образом

2 1 0

Y = С* D-1 = (-3; -1; 1) · -1/3 1/3 2/3

-2/3 -1/3 1/3

Y*=(-19/3; -11/3; -1/3),

т. е. y i = С*Х i , где Х i — коэффициенты разложения последней ите­рации, стоящие в столбцах векторов первоначального единичного базиса.

Итак, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней приба­вить соответствующее значение коэффициента линейной функции:

у 1 = 19/3 + 0 = — 19/3; y2 = -11/3 + 0 = -11/3; у 3 = -1/3+0 = -1/3. При этом плане max f = -46/3.

3. Симметричные двойственные задачи

Разновидностью двойственных задач линейного , программирования являются двойственные симметричные задачи, в ко­торых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойст­венные переменные налагается условие неотрицательности.

Исходная задача. Найти матрицу-столбец Х = (x1 , x2 , …, xn ), которая удовлетворяет системе ограничений

(1.12). АХ0 , Х >0

и минимизирует линейнуюфункцию Z = СХ.

Двойственная задача. Найти матрицу-строку Y = (y1 , y2 , …, yn ), которая удовлетворяет системе ограничений YA £C , Y ³0 и максимизирует линейную функцию f = YA 0 .

Систему неравенств с помощью дополнительных переменных мож­но преобразовать в систему уравнений, поэтому всякую пару симмет­ричных двойственных задач можно преобразовать в пару несимметрич­ных, для которых теорема двойственности уже доказана.

Используя симметричность, можно выбрать задачу, более удоб­ную для решения. Объем задачи, решаемой с помощью ЭВМ, ограни­чен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формули­ровке. При вычислениях без помощи машин использование двойствен­ности упрощает вычисления.

Исходная задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях

2x1 + 2x2 - x3 ³ 2,

x1 - x2 - 4x3 £ -3, xi ³ 0 (i=1,2,3)

x1 + x2 - 2x3 ³ 6,

2x1 + x2 - 2x3 ³ 3,

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.

Двойственная задача. Найти максимум линейной функции f = 2y1 + 3y2 + 6y3 + 3y4 при ограничениях

2y1 - y2 + y3 + 2y4 £ 1,

2y1 + y2 + y3 + y4 ³ 2,

-y1 + 4y2 - 2y3 - 2y4 ³ 3,

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

Для решения двойственной задачи необходимо ввести три допол­нительные переменные. Система ограничений не требует предваритель­ных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.

Двойственную задачу решаем симплексным методом (табл. 1.3).

Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), f max =21/2.

Оптимальный план исходной задачи находим, используя оценки ( m + 1)-й строки последней итерации, стоящие в столбцах A5 , A6 , A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0+ 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функ­ция достигает наименьшего значения: Zmin =21/2.

Т а б л и ц а 1.3

i Базис С базиса A0 2 3 6 3 0 0 0
A1 A2 A3 A4 A5 A6 A7

1

2

3

A5

A3

A7

0

0

0

1

2

3

2

2

-1

-1

1

4

1

1

-2

2

-1

-2

1

0

0

0

1

0

0

0

1

m + 1 Zi - Cj 0 -2 -3 -6 -3 0 0 0

1

2

3

A3

A6

A7

6

0

0

1

1

5

2

0

3

-1

2

6

1

0

0

2

-1

2

1

-1

2

0

1

0

0

0

1

m + 1 Zi - Cj 6 10 -9 0 9 6 0 0

1

2

3

A3

A2

A7

6

3

0

3/2

½

2

2

0

3

0

1

0

1

0

0

3/2

-1/2

4

½

-1/2

5

½

½

3

0

0

1

m + 1 Zi - Cj 21/2 10 0 0 9/2 3/2 9/2 0

4. Виды математических моделей двойственных задач

На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.

Несимметричные задачи

(1) Исходная задача Двойственная задача

Zmin = CX; f max = YA0 ;

AX = A0 ; YA £ С .

X ³ 0.

(2) Исходная задача Двойственная задача

Zmax = CX; f min = YA0 ;

AX = A0 ; YA ³ С .

X ³ 0.

Симметричные задачи

(3) Исходная задача Двойственная задача

Zmin = CX; f max = YA0 ;

AX ³A0 ; YA £ С .

X ³ 0. Y ³ 0.

(4) Исходная задача Двойственная задача

Zmax = CX; f min = YA0 ;

AX £A0 ; YA ³ С .

X ³ 0. Y ³ 0.

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

Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях

x1 – x2 – x3 £ 4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель долж­на иметь вид (3). Переход осуществляется умножением первого не­равенства на -1.

Исходная задача:

Zmin = 2x1 + x2 + 5x3 при ограничениях

-x1 + x2 + x3 ³ -4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

Двойственная задача:

f min = -4x1 + 5x2 + 6x3 при ограничениях

-y1 + y2 + 2y3 £ 2,

y1 – 5y2 - y3 £ 1, yi ³ 0 (i = 1, 2, 3).

2y1 + y2 + 3y3 £ 5,

Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального пла­на в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.

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

5. Двойственный симплексный метод

В п. 2 и п. 3 настоящего параграфа было показано, что для получения решения исходной задачи можно перейти к двой­ственной и используя оценки ее опти­мального плана, определить оптимальное решение исходной задачи.

Переход к двойственной задаче не обязателен, так как если рассмо­треть первую симплексную таблицу с единичным дополнительным ба­зисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются С j а оценками плана двойственной задачи – bi . Решим "двойственную задачу по симплексной таблице, в которой записана ис­ходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит на­звание двойственного симплексного метода,

Пусть необходимо решить исходную задачу линейного программиро­вания, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0 , Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA 0 при YA £ С. Допустим, что выбран такой базис D = (A 1 , А 2 , ..., А i , ..., А m ), при котором хотя бы одна из компонент вектора Х = D -1 A0 = (x1 , x2 , ..., xi , ..., xm ) отрицатель­ная (например, xi < 0), но для всех векторов Aj выполняется соотно­шение Zj – Cj £ 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = С баз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном бази­се X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двой­ственной задачи должны быть неотрицательными.

Таким образом, вектор Аi , соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствую­щий отрицательной оценке,— включить в базис двойственной задачи.

Для выбора вектора, включаемого в базис исходной задачи, просмат­риваем i строку: если в ней не содержатся x ij < 0, то линейная функция двойственной задачи не ограничена на многограннике реше­ний, а исходная задача не имеет решений. Если же некоторые x ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисля­ем q0j = min (xi /xij ) ³ 0 и определяем вектор, соответствующий maxq0j (Zj — Cj ) при решении исходной задачи на минимум и minq0j (Zj — Cj )при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необ­ходимо исключить из базиса исходной задачи, определяется направ­ляющей строкой.

Если q0j = min (xi /xij ) = 0, т. е. xi = 0, то x ij берется за раз­решающий элемент только в том случае, если x ij > 0. Такой выбор раз­решающего элемента на данном этапе не приводит к увеличению коли­чества отрицательных компонент вектора X . Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

В процессе вычислений по алгоритму двойственного симплексного метода условие Zj – Cj £ 0 можно не учитывать до исключения всех х i < 0, затем оптимальный план находится обычным симплексным ме­тодом. Это удобно использовать, если все х i < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q0j определить не по минимуму, а по максимуму отношений, т. е. q0j = max (xi /xij ) > 0.

Двойственным симплексным методом можно решать задачи линей­ного программирования, системы ограничений которых при положи­тельном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограниче­ний, а также размеры симплексной таблицы.

6. Список используемой литературы

1. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:21:34 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:52:02 09 февраля 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
16:25:38 30 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
11:52:59 24 ноября 2015
А нельзя было таблицы каким-то другим способом сделать? Очень неудобно.
Rasiel21:52:54 21 марта 2010Оценка: 2 - Плохо

Работы, похожие на Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151057)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru