Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 174

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

106 ГЛ. 5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

Полученное решение х0 = 20, xk = 16, х 3 = 6 оптимально. Заме­ тим, что в модифицированном симплекс-методе не обязательно

вычислять все Cj. Как только найдено Cj <с 0, соответствующий столбец может быть введен в базис.

5.2. Изменение исходной информации

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

минимизировать

Z = СВХВ + СдтХд-

при условиях

Вхв NxA, = Ь, хв, Хд,>0.

(1)

Рассмотрим хв в качестве базисных переменных. Тогда задачу

(1) можно представить в эквивалентной форме (2): минимизировать

z = свВ_1Ь -)- (cN —cBB_1N) хЛг

при условиях

 

 

 

хв Н• B_1NxA, = В-1Ь,

хв, хж> 0 .

 

(2)

Если хв — оптимальное решение,

то

 

 

 

1)

хв =

В_1Ь > 0 , т. е. хв прямо допустимо,

 

 

2)

сЛг — cBB*1N > 0,

т. е. хв двойственно допустимо. Следует

заметить,

что

прямая

допустимость не

зависит

от

вектора с,

а двойственная допустимость не зависит от вектора Ь.

 

Рассмотрим следующие виды изменения информации:

1.

Вектор

ограничений Ь изменяется

на b +

ЛЬ.

Поскольку

условие двойственной допустимости не зависит от Ь, решение ис­ ходной задачи хв остается двойственно допустимым. Решение исходной задачи хв будет также прямо допустимым, если

В-1Ь + В-1А Ь >0,

(3)

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

2. Вектор с заменяется на с + А (св, c N). Оптимальное реше­ ние исходной задачи остается прямо допустимым. Оно будет

 

 

 

УПРАЖНЕНИЯ

 

107

также двойственно допустимым, если

 

 

 

 

(сЛ- - cBB-JN) +

(Дсл. - AcbB^N) >

0.

(4)

Если

Лев = 0,

то условие (4)

примет вид

 

 

 

 

 

C j — яаj > — Ас,.

 

(5)

3.

Если

к

условиям

исходной задачи

добавить новый стол

бец an+i с ценой

сп+1, то оптимальное решение

хв останется

оптимальным,

если

 

 

 

 

 

 

 

С/и-1

^5-0.

 

 

Вмодифицированном симплекс-методе проверка этого условия

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

Упражнения

Решите следующие примеры при помощи модифицированного симплекс-метода.

1. Минимизировать

 

1

| 0

3

,

 

-

 

 

 

 

 

---- -£■ %2-\г ОХз —

 

~ х ь — 5,

 

 

 

 

 

 

X j> 0 (/' =

1, . ..,

5).

 

 

 

 

2. Максимизировать

 

 

 

 

 

 

 

 

 

w =

78xz -г 21х3 — 124а;5 +

6х7 +

1 7 xs 4-

ICteg

 

 

 

 

 

 

+ 2 х 7

—

х 8

— 3z9

-- 33,

 

 

 

 

— 2 х 7

+

4а:8

 

=

27,

 

 

 

 

 

 

+

 

+ Хд

=

86,

{Ответ: w —

1786, х7 =

92,5, х8 =

53, хд =

33; X j

=

0 для осталь­

ных j . )

 

 

 

 

 

 

 

 

 

 

3.Рассмотрим задачу линейного программирования:

 

Ах = Ь

max 1 сх

X {

х > 0

108

ГЛ. 5. МОДИФИЦИРОВАННЫЙ

СИМПЛЕКС-МЕТОД

 

Предположим, что хв—оптимальное базисное решение и В—

базисная матрица этого решения.

A-d, где X — скаляр, ad —

 

а) Пусть вектор b заменен на b +

ненулевой вектор из Ет. Найдите условие, при котором базис В

является оптимальным

для любого

X ^

0.

б) Пусть вектор с

заменен на

с +

Ag, где g — ненулевой

вектор из Еп, у которого компоненты, отвечающие базисным столбцам, равны нулю. Найдите условие, при котором базис В является оптимальным для всех X ^ 0. Объясните свои ответы.

ГЛАВА 6

МЕТОД ОДНОВРЕМЕННОГО РЕШЕНИЯ ПРЯМОЙ

II ДВОЙСТВЕННОЙ ЗАДАЧ

6.1. Взаимный метод решения прямой и двойственной задач (Балинский и Гомори [7[ и Тролл [184])

Симплексные таблицы, описанные в предыдущих главах,

состояли из (т + 1) X {т + п + 1) или (т + п + 1) X (п + 1)

элементов. В этой главе рассматривается таблица размера (т + 1) X (п + 1), которая обобщает ранее рассмотренные табли­ цы.

Пусть дана пара двойственных задач: прямая:

минимизировать

Х0 = Яоо “Г a Qlx l ~f" а 02х 2 + • • • Ч" а 0п%п

при условиях

— Х п+1

= a,\Q

~\~Cll2x2 “Ь ■• •

а 1пх п < 0 ,

 

Х п + т

— Ят о “ 1' & т \Х \ -j- (ljn 2X 2

• • •

d m n X n ^ O ,

(1)

 

 

X i

 

> 0 ,

 

Х п > о,

идвойственная: максимизировать

Уо = Яоо + ЯюУп-и + Я2оУтг+2 + •

ат0уп + т

при условиях

У п +i

Уп+2

У1 = я 01 + а ц У п +i + Л 2\У п+2 +

У п = Яоп + Я1п У п + 1 + Х 2пУ п + 2 +

■■ V V О р

J/n+m^O! (2)

•• • “Ь Ят1Уп+7П<>0>

•• • О - т п У п + т ^ - О .

Таблица 6.1 представляет собой компактную форму записи обеих задач. Она содержит всю необходимую информацию о задачах (1) и (2); xlt х2, . . ., хп — небазисные переменные прямой

н о

ГЛ. 6.

МЕТОД

ОДНОВРЕМЕННОГО

РЕШ ЕНИЯ

 

 

 

Таблица

6.1

 

 

 

 

 

1

Х\

 

х п

 

 

 

1

«00

«01

 

«0п

=

х 0

 

Уп+ 1

«10

«и

 

а 1п

—

хп+1

 

Уп+т

« т о

ат \

•

атп

=

— хп+т

 

 

= 2/0

= 2/1

 

= Уп

 

 

задачи, а уп+1: уп+2, ■. ., уп+т — небазисные переменные двой­ ственной. Базисные переменные обеих задач выражены через соответствующие небазисные переменные. Рассмотрим два типич­ ных уравнения из таблицы:

Т "

• • • ~f Q-ijXj “ Г

• • • +~ &inx n — x n+i%

a 0j + а ц у п +i +

• • • -г Ч ц У п +i +

• • • + ОтзУп+т = Уз-

Если а ц — ненулевой элемент (i ф О, j ф О ) , то он может быть

использован в качестве ведущего. Это означает, что переменная Xj заменит в базисе xn+i, a yn+i заменит в базисе переменную у }.

Поделив уравнения (3) на ац и выделив xj и уп+ц получим

«10

I «;1

; xn+i ■

= — Xj

aij

^ аЦxi +

113

(4)

аоз

аи ,,

 

77: У]

ТГ7 У п + т — Уп+1

а 13

Уп+i

а 13

 

 

Выражения (4) можно использовать для исключения небазисных переменных xj и yn+i в любом уравнении из табл. 6.1. Результаты преобразования можно проследить по табл. 6.2 и 6.3, где а —

ведущий элемент,

р — произвольный

элемент

ведущей строки,

у — произвольный

элемент ведущего

столбца,

6 — элемент из

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

Базисные решения для обеих задач можно получить из табли­ цы, положив небазисные переменные равными нулю. Текущие небазисные переменные записываются сверху или слева от табли­ цы. Например, табл. 6.4 получается из табл. 6.1 после одной итерации. Соответствующие базисные решения имеют вид'—x'n+i =

1,

f

*

t *

t

/

/

== ^ 10, • *

 

== О'ГП^ И y ±j

^ qI i • • •» У п

 

Смотрите также файлы