В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

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

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

Страница 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),

т. е. yi = С*Х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 = YA0.

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

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

Исходная задача. Найти минимальное значение линейной функции 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), fmax = 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

1 2 [3] 4

скачать реферат скачать реферат

Новинки
Интересные новости


Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2020 textreferat.com