Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
1.6. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД 41
min z = min(4x
1
+ 2x
2
);
−6x
1
− 2x
2
+ x
3
= −5;
−4x
1
− 3x
2
+ x
4
= −7;
x
1
+ 2x
2
+ x
5
= 3;
x
1
, x
2
≥ 0.
Перейдем к задаче максимизации:
max(−z) = max(−4x
1
− 2x
2
);
−6x
1
− 2x
2
+ x
3
= −5;
−4x
1
− 3x
2
+ x
4
= −7;
x
1
+ 2x
2
+ x
5
= 3;
x
1
, x
2
≥ 0.
Базисное решение образовано переменными x
3
= −5, x
4
= −7, x
5
= 3. Условие пря-
мой допустимости задачи не выполняется, так как имеются b
i
< 0. Условие двойственной
допустимости выполняется так как c
j
≥ 0. Начальная симплекс таблица выглядит сле-
дующим образом:
Переменные задачи
Базисные переменные x
1
x
2
x
3
x
4
x
5
Решение
−z 4 2 0 0 0 0
x
3
-6 -2 1 0 0 -5
x
4
-4 -3 0 1 0 -7
x
5
1 2 0 0 1 3
Таблица не оптимальна, так как выполняется двойственная допустимость, но не вы-
полняется прямая допустимость. Следуя алгоритму, находим min
b
i
<0
b
i
в нашей таблице это
строка, соответствующая базисной переменной x
4
, которая и будет ведущей.
Находим ведущий столбец из условия |
c
s
a
rs
| = min
a
rj
<0
|
c
j
a
rj
|. Переменной x
2
– соответству-
ет ведущему столбцу. При помощи метода Гаусса пересчитываем симплексную таблицу.
Переменные задачи
Базисные переменные x
1
x
2
x
3
x
4
x
5
Базисное решение
−z 1
1
3
0 0
2
3
0 −4
2
3
x
3
−3
1
3
0 1 −
2
3
0 −
1
3
x
2
4
3
1 0 −
1
3
0 2
1
3
x
5
−1
2
3
0 0
2
3
1 −1
2
3
42 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Таблица не оптимальна. Ведущая строка x
3
, ведущий столбец x
1
. После пересчета
получаем таблицу:
Переменные задачи
Базисные переменные x
1
x
2
x
3
x
4
x
5
Базисное решение
−z 0 0 0 1
1
5
4
5
6
x
3
0 0 1 -2 -2 3
x
2
0 1 0
1
5
4
5
1
x
1
1 0 0 −
2
5
−
3
5
1
Таблица оптимальна, так как является прямо-допустимой и двойственно-допустимой.
Из таблицы получаем значение z
∗
= 6 и оптимальное решение x
∗
1
= 1, x
∗
2
= 1, x
∗
3
= 3.
1.6.1 Задачи для самостоятельного решения
Напишите двойственные задачи для прямых задач ЛП:
1.6.1 1.6.2
min z = min(2x
1
− 2x
2
);
−x
1
+ x
2
≥ −3;
2x
1
+ 3x
2
≤ 5; x
1
, x
2
≥ 0.
max z = max(5x
1
+ 6x
2
);
x
1
+ x
2
= 5;
−x
1
+ 5x
2
≥ 3;
4x
1
+ 7x
2
≤ 8.
x
1
− ∀, x
2
≥ 0.
1.6.3 1.6.4
min z = min(5x
1
− 2x
2
);
−x
1
+ x
2
≤ −3,
2x
1
+ 3x
2
≥ 5,
x
1
, x
2
≥ 0.
max z = max(5x
1
+ 6x
2
);
x
1
+ x
2
= 5;
−x
1
+ 5x
2
≥ 3;
4x
1
+ 7x
2
≤ 8;
x
1
− ∀, x
2
≥ 0.
1.6. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД 43
1.6.5 1.6.6
max z = max(x
1
− 10x
2
+ 2x
3
− x
4
+ 7x
5
);
2x
1
− x
2
≤ 1,
x
1
− x
2
+ 2x
3
− x
4
+ x
5
≥ 4,
x
2
+ x
3
− x
4
= 0,
x
1
− x
3
+ 2x
5
≥ 3;
x
1
≥ 0, x
5
≥ 0.
min z = min(3x
1
+ 2x
2
);
x
1
− 2x
2
≤ 3;
2x
1
− x
2
≤ 10;
3x
1
− x
2
≥ −5;
−x
1
− x
2
≥ 3;
x
1
, x
2
≥ 0.
Решите двойственным симплекс-методом.
1.6.7 1.6.8
min z = min(5x
1
+ 6x
2
);
x
1
+ x
2
≥ 2;
4x
1
+ x
2
≥ 4;
x
1
, x
2
≥ 0.
max z = max(−5x
2
− 7x
4
);
−10x
1
+ x
3
+ x
4
= −16;
x
1
− 3x
2
− 3x
4
= −12;
−6x
2
+ 2x
4
+ x
5
= −17;
x
1
, x
2
, x
3
, x
4
, x
5
≥ 0.
1.6.9 1.6.10
max z = max(−2x
2
− x
4
);
5x
1
+ 5x
2
− 20x
5
= −2,
−5x
2
+ 10x
3
+ 5x
5
= −3,
5x
2
+ 15x
4
− 15x
5
= −1;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(−x
3
− 2x
4
);
2x
3
+ 8x
4
+ 2x
5
= −1,
6x
2
− 4x
3
+ 2x
4
= −3,
2x
1
+ 2x
3
− 6x
4
= −1;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
1.6.11 1.6.12
max z = max(−x
1
− 3x
4
);
12x
1
+ 6x
2
− 18x
4
= −1,
12x
1
+ 6x
3
− 18x
4
= −1,
3x
1
− 6x
4
+ 3x
5
= −1;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(−2x
1
− 3x
2
);
−4x
1
+ 2x
2
+ 2x
5
= −3,
2x
1
− 4x
2
+ 2x
3
= −1,
−2x
1
− 2x
2
+ 2x
4
= −5;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
1.6.13 1.6.14
max z = max(−5x
1
− 4x
2
);
1x
1
+ 2x
2
− 1x
3
= −2,
−4x
1
− 3x
2
− 1x
4
= −12,
−4x
1
− 4x
2
− 1x
3
− 1x
4
− 1x
5
= −10;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(−x
1
− 7x
4
);
−4x
1
+ 2x
3
− 2x
4
= −7,
2x
1
+ 2x
2
− 2x
4
= −1,
−6x
1
+ 2x
4
+ 2x
5
= −5;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
44 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
1.6.15 1.6.16
max z = max(−x
2
− 4x
5
);
−1x
2
+ 1x
3
+ −1x
5
= −3,
1x
1
+ 2x
2
− 4x
5
= −1,
−1x
2
+ 1x
4
+ 1x
5
= −1;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(−x
2
− 6x
4
);
5x
1
− 5x
2
+ 1x
3
= −1,
+5x
2
+ 1x
3
− 2x
4
= −1,
−10x
2
+ 1x
4
+ 1x
5
= −1;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
1.6.17 1.6.18
max z = max(−2x
1
− 1x
2
− 15x
3
);
6x
1
+ 6x
3
+ 6x
4
= −1,
12x
1
+ 6x
2
− 18x
3
= −11,
−24x
1
+ 6x
3
+ 6x
5
= −7;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(−1x
2
− 2x
4
);
2x
1
− 2x
2
− 2x
4
= −5,
1x
2
− 3x
4
+ 1x
5
= −1,
−1x
2
+ 1x
3
+ 1x
4
= −2;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
1.6.19 1.6.20
max z = max(−2x
2
− 4x
4
);
−6x
1
+ 3x
2
= −1,
−3x
2
+ 1x
3
− 3x
4
= −2,
+6x
2
− 12x
4
+ 1x
5
= −2;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(1 − 2x
2
− 3x
4
);
4x
2
+ 4x
3
− 8x
4
= −3,
2x
1
+ 4x
2
− 6x
4
= −1,
−8x
2
+ 2x
4
+ 4x
5
= −7;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
1.6.21 1.6.22
max z = max(−x
1
− 10x
2
);
−2x
1
− 2x
2
+ 2x
5
= −1,
−2x
1
+ 2x
2
+ 1x
3
= −2,
−4x
1
+ 2x
2
+ 1x
4
= −1;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
max z = max(−x
1
− 2x
5
);
21x
1
+ 7x
3
− 28x
5
= −1,
28x
1
+ 7x
2
− 49x
5
= −2,
14x
1
+ 28x
4
− 49x
5
= −5;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
Глава 2
Задачи транспортного типа
2.1 Формулировка транспортной задачи
Пусть на заводах A
1
, A
2
, . . . , A
m
(пункты производства, пункты предложения), произ-
водится некоторый однородный продукт, где a
i
, i =
1, m – объем производства в A
i
в
плановый период. Продукт потребляется рынками B
1
, B
2
, . . . , B
n
, (пункты потребления,
пункты спроса), с объемом потребления b
j
, j = 1, n. Обозначим через c
ij
– стоимость
перевозки единицы продукта из пункта производства A
i
в пункт потребления B
j
. Обо-
значим через x
ij
– объем перевозок продукта из A
i
в B
j
по плану. Необходимо определить
такой план перевозок X
∗
= {x
∗
ij
}, при котором спрос каждого из рынков был удовле-
творен, весь объем продукции был вывезен с каждого пункта производства и при этом
суммарные затраты по перевозке продукции были бы минимальными.
Транспортная задача может быть задана сетевым способом.
Рис.2.1.1. Транспортная сеть
45
46 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
На рис. 2.1.1 изображена транспортная сеть с m пунктами производства и n пунк-
тами потребления. Пунктам производства и потребления соответствуют вершины сети,
ребро, соединяющее пункт производства и пункт потребления, показывает направление,
по которому может перевозиться продукция, a
i
– объем производства в A
i
, b
j
– объем
потребления в B
j
, c
ij
– транспортные затраты по перевозке продукции из A
i
в B
j
; x
ij
–
объем перевозимой продукции из A
i
в B
j
по плану X.
Транспортная задача так же может быть задана в виде таблицы.
Пункты Пункты потребления Предложение, a
производства B
1
. . . B
j
. . . B
n
A
1
c
11
. . . c
1j
. . . c
1n
a
1
x
11
x
1j
x
1n
. . . . . . . . . . . . . . . . . . . . .
A
i
c
i1
. . . c
ij
. . . c
in
a
i
x
i1
x
ij
x
in
. . . . . . . . . . . . . . . . . . . . .
A
m
c
m1
. . . c
mj
. . . c
mn
a
m
x
m1
x
mj
x
mn
Спрос, b b
1
. . . b
j
. . . b
n
Табл.2.1.1. Транспортная таблица.
2.2 Каноническая транспортная модель
Математическая модель транспортной задачи выглядит следующим образом:
min z = min
m
P
i=1
n
P
j=1
c
ij
x
ij
;
n
P
j=1
x
ij
= a
i
, i =
1, m;
m
P
i=1
x
ij
= b
j
, j =
1, n;
x
ij
≥ 0;
x
ij
∈ Z; (x
ij
− целые)
Утверждение 2.2.1 Для того чтобы транспортная задача имела допустимое реше-
ние необходимо и достаточно, чтобы выполнялось условие баланса:
2.3. МЕТОДЫ НАХОЖДЕНИЯ НАЧАЛЬНОГО ОПОРНОГО ПЛАНА 47
m
X
i=1
a
i
=
n
X
j=1
b
j
.
Транспортная модель называется сбалансированной или закрытой, если выполнено
условие баланса. В противном случае модель называют несбалансированной (откры-
той). Любую транспортную задачу можно сбалансировать путем введения фиктивного
пункта производства (потребления).
Определение 2.2.1 Опорным планом транспортной задачи называется допусти-
мое базисное решение транспортной модели.
Опорный план X называется невыроженным, если число положительных элемен-
тов матрицы X равно m + n − 1. В противном случае опорный план называется вырож-
денным.
Проверка допустимого плана на опорность (метод вычеркивания)
• Вычеркнуть строки в X, содержащие не более одного положительного элемента.
• В полученной матрице вычеркнуть все столбцы, содержащие не более одного по-
ложительного элемента.
• Далее опять вычеркиваются строки, а затем столбцы и т.д.
Если все строки и столбцы вычеркнуты, то рассматриваемый допустимый план –
опорный. В противном случае он не является опорным. Тогда осталась невычеркнутой
подматрица, содержащая не менее двух строк и столбцов, у которых по крайней мере
два положительных элемента. Последнее означает, что в этой подматрице можно постро-
ить цикл из положительных элементов. Рассмотрим теперь эвристические методы для
нахождения начального опорного плана.
2.3 Методы нахождения начального опорного плана
2.3.1 Метод северо-западного элемента
Начинаем заполнение матрицы X со свободного северо-западного элемента таблицы
x
11
= min{a
1
, b
1
}, который будет первым базисным элементом. Корректируем значения
спроса и предложения:
a
1
= a
1
− x
11
, b
1
= b
1
− x
11
.
48 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
В результате строка (если a
1
= 0), либо столбец ( если b
1
= 0) дополняются нулями и
вычеркиваются. Обязательно либо x
1j
= 0, j = 2, n, либо x
i1
= 0, i = 2, m.
Переходим к заполнению свободного северо-западного элемента матрицы X. Процесс
продолжается до тех пор пока не будет заполнена вся матрица X. Метод используется
только для нахождения начального опорного плана и требует дальнейшей оптимизации,
с использованием компьютера. Недостаток – не использует информацию о затратах, а
поэтому часто дает неэкономичное решение.
2.3.2 Метод минимального элемента
Метод использует процедуру, аналогичную процедуре метода северо-западного угла. От-
личие состоит в том, что всегда заполняется свободный элемент, имеющий минимальные
затраты. Метод используется для нахождения начального опорного плана при ручной
оптимизации.
2.3.3 Приближенный метод Фогеля (ПМФ)
1. Вычислить штраф для каждой строки(столбца), вычитая наименьший элемент
этой строки (столбца) из следующего за ним по величине элемента той же стро-
ки(столбца).
2. Отметить строку(столбец) с наибольшим штрафом. Если таких строк (столбцов)
несколько, выбрать среди них любую строку или столбец. В отмеченной строке
(столбце) выбрать свободный элемент с наименьшей стоимостью и придать ему
наибольшее значение.
Скорректировать объем производства и спрос. Вычеркнуть строку или столбец,
как в методе северо-западного элемента. Скорректировать штрафы по строкам и
столбцам. Продолжить вычисления согласно п.2.
3. Если остается невычеркнутым только одна строка (столбец) с положительным объ-
емом производства (спросом), закончить вычисления в этой строке (столбце), ис-
пользуя метод минимального элемента.
В практике метод Фогеля используется, только, как оценочный метод.
2.3. МЕТОДЫ НАХОЖДЕНИЯ НАЧАЛЬНОГО ОПОРНОГО ПЛАНА 49
2.3.4 Прямая и двойственная транспортная задача
Если рассматривать транспортную задачу как прямую задачу линейного программиро-
вания, то двойственная к ней задача будет иметь вид:
max w = max
n
P
j=1
b
j
v
j
−
m
P
i=1
a
i
u
i
;
v
j
− u
i
≤ c
ij
, i =
1, m, j = 1, n,
где (−u
i
), i =
1, m, v
j
, j = 1, n – двойственные переменные.
Теорема двойственности для транспортной задачи.
Теорема 2.3.1 В условиях баланса прямая и двойственная транспортная задач а име-
ют оптимальные решения Y
∗
= {−u
∗
1
, . . . , −u
∗
m
, v
∗
1
, . . . , v
∗
n
} и X
∗
= {x
∗
ij
}, при этом
n
X
j=1
m
X
i=1
c
ij
x
∗
ij
=
n
X
j=1
b
j
v
∗
j
−
m
X
i=1
a
i
u
∗
i
.
Каноническая теорема равовесия.
Теорема 2.3.2 Для того чтобы допустимые решения Y
∗
= {−u
∗
1
, . . . , −u
∗
m
, v
∗
1
, . . . , v
∗
n
}
и X
∗
= {x
∗
ij
} для прямой и двойственной задач соответственно б ыли оптимальными
решениями соответствующих задач необходимо и достаточно, чтобы v
∗
j
−u
∗
i
= c
ij
для
x
∗
ij
> 0 и x
ij
= 0 для v
∗
j
− u
∗
i
< c
ij
.
2.3.5 Метод потенциалов решения транспортной задачи
Метод потенциалов предназначен для нахождения оптимального решения сбалансиро-
ванной транспортной задачи.
Алгоритм метода потенциалов.
ИТЕРАЦИЯ
1. Пусть X
0
= {x
0
ij
} -невырожденный начальный опорный план, построенный одним
из методов нахождения начального допустимого решения.
• Строим множество индексов S
0
= {(i, j)|x
0
ij
> 0}.
• Решаем систему потенциалов: v
0
j
− u
0
i
= c
ij
, где (i, j) ∈ S
0
, полагая u
0
1
= 0.
Пусть v
0
j
, j =
1, n, u
0
i
, i = 1, m – решения этой системы (потенциалы опорного
плана X
0
).
50 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
2. Находим невязки плана X
0
: ∆
ij
= c
ij
− (v
0
j
− u
0
i
), i = 1, m, j = 1, n.
• Если ∆
ij
= c
ij
− (v
0
j
− u
0
i
) ≥ 0, для всех j = 1, n, i = 1, m, то X
0
= {x
0
ij
} – опти-
мальный план транспортной задачи, а потенциалы Y
0
= (−u
0
1
, . . . , −u
0
m
, v
0
1
, . . . , v
0
n
)
– оптимальное решение двойственной задачи.
3. В противном случае план можно улучшить. Для этого находим ∆
sr
= min ∆
ij
< 0
(соответствующая переменная x
sr
вводится в базис).
4. Для построения нового плана X
1
в X
0
строится цикл, начинающийся с элемента
sr и использующий только базисные клетки таблицы.
5. Для нахождения X
1
пропускаем максимально возможный транспортный поток Θ
+
по найденному циклу. Для этого:
• помечаем клетки цикла поочередно знаками
”
+“и
”
−“, начиная с клетки rs.
• в клетки, помеченные знаком
”
−“, находим минимальный элемент Θ
+
.
• из объемов перевозок, стоящих в клетках, помеченных знаком
”
−“, вычитаем
Θ
+
.
• прибавляем величину Θ
+
к объемам перевозок в клетках, помеченных
”
+“. В
результате получаем новый опорный план X
1
. Переходим к пункту 1 новой
итерации с планом X
1
.
2.4 Примеры
Пример 2.4.1. Пусть транспортная задача задана транспортной таблицей:
Предложение
15 5 25 16 20
x
11
x
12
x
13
x
14
17 12 14 25 35
x
21
x
22
x
23
x
24
5 19 21 23 10
x
31
x
42
x
33
x
34
Спрос 10 20 20 15
Табл.2.4.1. Транспортная таблица.