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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

2.2. ТАБЛИЦА

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

51

 

Таблица 2.1

 

 

 

1

Ч

х 2

х 3

ч

х 5

 

- и

0

0

- 1

—1

- 1

 

2

1

0

1

- 1

2

 

1

0

1

- 1

+2* —1

 

они являются базисными переменными этой таблицы. Если поло­ жить базисные переменные равными числам из 0 -го столбца,

то получим допустимое решение. В 0-й строке имеется три отри­ цательных элемента с одним и тем же значением (в § 2.3 будет дано правило выбора в таких случаях). Произвольно в качестве веду­ щего выберем столбец при хк.

Вэтом столбце имеется только один положительный элемент

а24 = 2; выберем его в качестве ведущего. В таблице он обозначен

звездочкой. Разделив все элементы ведущей строки на ведущий элемент, получим на месте а24 единицу. Затем применим процедуру

исключения Гаусса, чтобы сделать аи = 0 (i = 0,1). Результат приведен в табл. 2.2. Заметим, что в этой таблице переменная х4

 

 

Таблица 2.2

 

 

 

 

Таблица

2.3

 

 

 

1

Xi х2

х3 *4 х5

 

1

Xi Х2 х3 Ч Ч

—Z —21/2

0

1/2

- 3 /2

0

— 3/2

—Z

- 3

3

2

0

0

3

Х1

5/2

1

1/2

1/2*

0

3/2

хз

5

2

1

1

0

3

xi

1/2

0

1/2

- 1 /2

1

—1/2

#4

3

1

1

0

1

1

заменила в базисе х%(стала базисной).

 

 

 

 

 

 

 

Среди отрицательных элементов 0-й строки можно выбрать

либо х3, либо х5. Произвольно выберем

в

качестве

ведущего

третий столбец.

В третьем столбце только элемент а13 положите­

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

что переменная х3 заменила в базисе xi.

В табл. 2.3

нет отрица­

тельных чисел,

a0j ^ 0

(/ = 1, . . ., 5),

т. е. она

оптимальна.

Оптимальным

решением

является х3 =

5, ж4 = 3,

xt — Хп —

= х5 = 0.

 

 

 

 

4 *

52

ГЛ. 2. СИМПЛЕКС-МЕТОД

Пример 2. Рассмотрим задачу: минимизировать

z = ад + ад + 2xs + 8ад,

при условиях

2xi —

ад +

Зад — 2*4 =

3,

(1)

—Xi +

За:2 — 4а:з +

4ад =

1,

(2)

Xj >

0

(]

= I,

. . 4).

 

Это представление не является диагональной фо'рмой относи­ тельно каких-либо переменных. Пусть ад и ад — начальные базис­ ные переменные. Умножив уравнение (1) на 4 и сложив с уравне­ нием (2), умноженным предварительно на 3, получим

5а:! + 5ад + 4ад = 15,

что равносильно

5

5

.

15

/о \

x i +

 

х г + x k —

■

(3 )

Умножив уравнение (1) на 2 и сложив с уравнением (2), получим

или,

эквивалентно,

Зад +

ад +

2а:з =

7,

 

 

 

 

3

,

1

.

7

 

 

 

. . .

 

 

 

 

 

 

 

 

 

 

 

 

 

~2

 

хгЛ~ хз — ~2 •

 

 

 

(4)

Используя

уравнения

(3)

и

(4),

запишем

информацию

о

задаче

в

виде табл. 2.4. Поскольку в нулевой строке относительные

 

 

 

Таблица

2.4

 

 

 

 

 

Таблица

2.5

 

 

 

 

1

X i

х2

х3

Ч

 

 

1

X i

х2

Ч ч

—

Z

0

1

1

2

8

 

— Z

—37

—12

—10

0

0

ч

 

15/4

5/4

5/4

0

1

 

ч

15/4

5/4

5/4

0

1

Ч

 

7/2

3/2

1/2

1

0

 

ч

7/2

3/2*

1/2

1

0

оценки, соответствующие базисным переменным, ненулевые, умно­ жим первую строку на 8, а вторую — на 2 и вычтем их из нулевой строки. Результат приведен в табл. 2.5.

Поскольку наименьшая

отрицательная оценка расположена

в столбце под ад, введем в

базис переменную ад. Проверка отно­

шения дает min ( у / у > у / т ) — 7/з, т- е- 3/г должен стать веду­

щим элементом. Результат преобразования приведен в табл. 2.6.

2.3. НАЧАЛЬНЫЙ ДОПУСТИМЫЙ БАЗИС И ВЫРОЖДЕННОСТЬ

53

Единственной отрицательной оценкой является — 6; пере­ менная х2 должна быть введена в базис. Из проверки отношения

5 / 5

7

/1 \

(Т / Т ’

Т

Т ) = 1 слеДУет> чт0 ведущим элементом должен

стать 5/6. Результат преобразования показан в табл. 2.7.

 

 

Таблица 2.6

 

 

 

 

Таблица

2.7

 

 

1

X i

х2

Ч

Ч

 

1

хк х2

х3

Ч

—Z

—9

0

—6

8

0

— Z

—3

0

0

2

36/5

хк

5/6

0

5/6*

- 5 /6

1

хг

1

0

1

- 1

6/5

X i

7/3

1

1/3

2/3

0

X i

2

1

0

1

- 2 /5

Поскольку все элементы aoj (j = 1, 2, 3, 4)

неотрицательны,

табл. 2.7 оптимальна. Оптимальным решением

является z — 3,

Х\ = 2 , х2 = 1, х3 = хк — 0.

 

2.3.Начальный допустимый базис и вырожденноеть

Вэтом параграфе будет изучена техника получения начального допустимого базиса. Пусть задача линейного программирования записана в канонической форме:

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

Z —

C j X j

 

при условиях

j=l

 

 

 

2 Q ' i j X j — bi

(j—1,

., т),

1=1

0 = 1,

., п).

X j > 0

Все bt можно сделать неотрицательными, умножив, если надо, соответствующее уравнение на —1. Тогда можно добавить в каж­ дое уравнение искусственную переменную x f *) таким образом, чтобы из искусственных переменных образовать начальный базис

Х 1

~Н а И х 1

—)—<^12^2 “Н • ■• Н~а 1п х п —

xt

+ 0-uXi

+ а2гхг +

а2пхп = Ъ3,

х т Ят1х 1 “Ь &т2.х 2 ~Ь • • • “НЯт пх п — Ьт .

г) Искусственные переменные должны быть неотрицательными.

54

ГЛ. 2. СИМПЛЕКС-МЕТОД

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

2 dijX j^bi,

О

то, добавив слабую переменную в каждое неравенство, получим

J]aijXj + Si = bi.

j

Если bt ^ 0, то S; можно использовать в качестве начальных базисных переменных.

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

z = 2

C j X j -f 2 M ixf,

3

г

где M t — достаточно большие положительные числа. (В задаче максимизации М г должны быть большими по абсолютной величине отрицательными числами.) Этот способ, называемый методом штра­ фа, предложен Чарнесом, Купером и Хендерсоном [26]. Идея метода соответствует тому, что искусственным переменным при­ даются заведомо большие цены. Такой способ приводит к нулевым значениям искусственных переменных в оптимальном решении.

Существует и другой способ получения начального допусти­ мого базиса. В этом способе, как и в первом, в качестве начальных базисных переменных используются искусственные переменные. Рассматривается новая целевая функция §, представляющая собой сумму искусственных переменных. Требуется минимизировать |, используя z-уравнение как одно из ограничений. Если исходная система уравнений имеет допустимое решение, то все искусствен­ ные переменные должны стать равными нулю. Следовательно,

минимальное значение | = 2 х? должно быть равно нулю. Если

г

min g > 0, то исходная система уравнений не имеет допустимых решений. Если min g = 0, то можно опустить целевую функцию g = 2 xi и использовать оптимальный базис g-формы в качестве

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