Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 205 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

Составители: 

Рубрика: 

205
A
2
B
2
A
2
B
4
A
2
B
n+
1
A
4
B
2
A
4
B
4
Рис.5.6
Сформулируем основные
свойства циклов
в ламбда-задаче.
Цикл представляет собой ломаную
(не обязательно замкнутую)
линию, одна из
вершин которой находится в одной из свободных клеток, остальные
— в
базисных
клетках.
Если
в опорном плане
число базисных клеток равно
m+n-1,
то
для каждой
свободной клетки можно построить цикл
пересчета и притом
только один.
Максимальное число вершин в цикле
т+п
-1
,
минимальное— четыре.
Каждая из вершин, находящихся в клетках столбцов
В
1
,
В
2
,…,
В
n
,
обязательно
имеет двустороннюю связь с другими вершинами
(с учетом шлейфа могут иметь и
трехстороннюю).
Вершины, находящиеся в базисных клетках столбца B
n+1
,
имеют только
одностороннюю связь через шлейф.
Если для свободной клетки удается построить замкнутый цикл
по клеткам,
связанным с столбцами
В
1
. . .
В
n
, то в этом случае шлейфом непосредственно или через
другие клетки
соединяют его только с одной базисной клеткой столбца
B
n+1
.
В случаях, когда для какой-то свободной клетки
не удается построить замкнутый
цикл
по клеткам, связанным с столбцами
В
1
. . .
В
n
,
соединяют его шлейфами с двумя
базисными клетками столбца B
n+1
.
Возвратимся к рассматриваемому примеру. Для перехода к лучшему плану
необходимо провести перераспределение заданий по циклу пересчета клетки
A
2
B
2
.
Переменные, не вошедшие в этот цикл пересчета (
x
12
=100,
x
21
=100 и
x
33
=150), переносятся
в новый план без изменения.
Перераспределение поставок в транспортной задаче выполнялось просто, без
затруднений. В ламбда-задаче перераспределение по циклу значительно усложняется в
связи с наличием показателей
λ
ij
в условии задачи.
В ламбда-задаче без предварительных расчетов нельзя заранее определить, какими
будут (положительными или отрицательными) вершины цикла, входящие в шлейф.
Нельзя также заранее по внешним признакам определить наименьшую переменную на
вершине, отмеченной знаком "-".
Для установления знака в вершине и определения минимальной переменной
перераспределения выполняют ряд последовательных расчетов, сущность которых
заключается в следующем.
Прежде составляется и решается специальная система уравнений. Обозначим
показатели, характеризующие размер изменения переменных
x
ij
при перераспределении
их по циклу,
a
ij
.

Страницы