Постановка задачи, Случаи вырождения и способы их преодоления - Транспортная задача линейного проектирования

Цель работы.

В городе имеется четыре АТС со свободной номерной емкостью (1,2,3,4). Известно количество свободных телефонных номеров на каждой станции. Также имеется пять районов (1,2,3,4,5), которые требуют телефонизации. Известно также расстояние от каждой АТС до центра каждого района. Нужно разделить имеющуюся телефонную емкость между районами так, чтобы расход кабеля и стоимость всей операции были минимальными. (Номера от одной АТС могут попадать в разные районы).

Определение транспортной задачи.

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

Подсчитаем суммы номерных емкостей: количество необходимых номеров: 30+25+45+30+35=165; количество свободных номеров: 25+30+40+55=150. Т. к. в нашем случае число заявок превышает количество свободных номеров, то задача является открытой. Значит, какие-то районы недополучат требуемых телефонных номеров. Чтобы сбалансировать задачу, необходимо ввести фиктивную строку с нулевыми расстояниями. Тогда задачу можно представить в виде матрицы следующего вида: сверху в строку пишем районы, которые нуждаются в телефонизации, в первый столбец пишем станции 1,2,3,4,5, в нижней строке и соответствующем столбце пишем потребность районов в телефонных номерах. В последнем столбце пишем свободную номерную емкость. Матрица имеет вид:

Таблица 1

Телефонные станции

Районы

Свободные номера

I

II

III

IV

V

1

1

2

6

3

2

25

2

6

2

2

1

3

30

3

2

1

2

1

3

40

4

2

5

6

4

6

55

5

0

0

0

0

0

Заявки

30

25

45

30

35

Целью решения задачи является отыскание такого распределения ресурсов по работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.

Поставим эту задачу как задачу линейного программирования. Обозначим xij - количество номеров, отдаваемых i-й телефонной станцией j-району. Неотрицательные переменные xij тоже можно записать в виде матрицы:

X11 x12 ...x1n

X21 x22 ...x2n (1)

................

Xm1 xm2 ...xmn,

Которая коротко обозначается (xij). Совокупность чисел (xij) называется "планом перевозок", а сами величины xij - "перевозками". Эти неотрицательные переменные должны удовлетворять следующим условиям:

1. Суммарное количество номеров, отдаваемых каждой АТС во все районы, должно равняться количеству свободных номеров в данной АТС. Это даст нам m условий-равенств:

X11+x12+...+x1n=a1,

X21+x22+...+x2n=a2, (2)

.......................

Xm1+xm2+...+xmn=am.

2. Суммарное количество номеров, отдаваемых в каждый район от всех АТС, должно быть равно заявке, поданной данным районом. Это даст нам n условий-равенств:

X11+x12+...+x1n=b1,

X21+x22+...+x2n=b2, (3)

.......................

Xm1+xm2+...+xmn=bm.

3. суммарная стоимость всех операций, т. е. сумма величин xij, умноженных на соответствующие стоимости сij, должна быть минимальной:

S=cijxij=min, (4)

I=1 j=1

Где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j.

У нас задача линейного программирования с условиями-равенствами (2), (3) и минимизируемой линейной функцией (4). Все коэффициенты в условиях (2), (3) равны единице. Условия-равенства (2), (3) не являются линейно-независимыми. Число линейно-независимых среди уравнений (2), (3) равно m+n-1. Общее число переменных xij в нашей задаче равно m*n, число базисных переменных будет равно m+n-1, а число свободных переменных k=m*n-(m+n-1)=(m-1)*(n-1).

Любой план перевозок называется допустимым, если он удовлетворяет условиям (2), (3) (все заявки удовлетворены, все запасы исчерпаны). Допустимый план будет называться опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны нулю. План будет называться оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок.

Случаи вырождения и способы их преодоления

Выше отмечалось, что число занятых мест в таблице должно быть равно m+n-1. Однако на практике встречаются случаи, когда в процессе решения оно сокращается.

Это явление называется вырождением. Для преодоления этого в одну из освободившихся клеток ставится 0 и эта клетка считается занятой. Иногда приходится встречаться с вырождением уже при составлении исходного решения. Вырождения в этом случае можно избежать, переставляя местами столбцы и строки.

Похожие статьи




Постановка задачи, Случаи вырождения и способы их преодоления - Транспортная задача линейного проектирования

Предыдущая | Следующая