На какую максимальную величину можно уменьшить запас второго ресурса, не уменьшая дохода - Распределение транспортных ресурсов

X1

X2

S1

S2

S3

X1

1

0

5

0

0

150

Х2

0

0

-20

-40

-40

230

S3

0

1

-15

50

10

100

0

0

65

170

0

1900

Находим опорный план методом Фогеля:

1. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце.

Строка 1: c1,4 - c1,2 = 1

Строка 2: c2,1 - c2,4 = 0

Строка 3: c3,4 - c3,1 = 1

Столбец 1: c2,1 - c3,1 = 1

Столбец 2: c3,2 - c1,2 = 1

Столбец 3: c2,3 - c3,3 = 1

Столбец 4: c2,4 - c3,4 = 0

Если одновременно несколько строк(столбцов) имют одинаковую разницу двух минимальных тарифов, то выберем строку(столбец), содержащую клетку с наименьшим тарифом сI, j

Максимальная разница двух минимальных тарифов в строке находится в строке 3.

Максимальная разница двух минимальных тарифов в столбце находится в столбце 1.

Заполняем клетку (2,1), имеющую минимальный тариф.

2. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце

Строка 1: c1,4 - c1,2 = 1

Строка 2: c2,4 - c2,3 = 1

Строка 3: c3,4 - c3,2 = 2

Столбец 1: нет свободных клеток

Столбец 2: c3,2 - c1,2 = 1

Столбец 3: c2,3 - c3,3 = 1

Столбец 4: c2,4 - c3,4 = 0

Максимальная разница двух минимальных тарифов в строке находится в строке 3.

Максимальная разница двух минимальных тарифов в столбце находится в столбце 3.

Заполняем клетку (3,4), имеющую минимальный тариф.

3. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце

Строка 1: c1,2 - c1,3 = 2

Строка 2: c2,3 - c2,2 = 8

Строка 3: c3,2 - c3,3 = 0

Столбец 1: нет свободных клеток

Столбец 2: c3,2 - c1,2 = 1

Столбец 3: c2,3 - c3,3 = 1

Столбец 4: нет свободных клеток

Максимальная разница двух минимальных тарифов в строке находится в строке 2.

Максимальная разница двух минимальных тарифов в столбце находится в столбце 3.

Заполняем клетку (2,3), имеющую минимальный тариф.

4. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце.

Строка 1: c1,2 - c1,3 = 2

Строка 2: нет свободных клеток

Строка 3: c3,2 - c3,3 = 0

Столбец 1: нет свободных клеток

Столбец 2: c3,2 - c1,2 = 1

Столбец 3: c3,3 - c1,3 = 3

Столбец 4: нет свободных клеток

Максимальная разница двух минимальных тарифов в строке находится в строке 1.

Максимальная разница двух минимальных тарифов в столбце находится в столбце 3.

Заполняем клетку (3,3), имеющую минимальный тариф.

5. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце.

Строка 1: c1,2 - c1,3 = 2

Строка 2: нет свободных клеток

Строка 3: нет свободных клеток

Столбец 1: нет свободных клеток

Столбец 2: c1,2 - c1,2 = 0

Столбец 3: c1,3 - c1,3 = 0

Столбец 4: нет свободных клеток

Максимальная разница двух минимальных тарифов в строке находится в строке 1. Максимальная разница двух минимальных тарифов в столбце находится в столбце 2.

Заполняем клетку (1,2), имеющую минимальный тариф.

6. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце.

Строка 1: c1,3 - c1,3 = 0

Строка 2: нет свободных клеток

Строка 3: нет свободных клеток

Столбец 1: нет свободных клеток

Столбец 2: нет свободных клеток

Столбец 3: c1,3 - c1,3 = 0

Столбец 4: нет свободных клеток

Максимальная разница двух минимальных тарифов в столбце находится в столбце 3.

Заполняем клетку (1,3), имеющую минимальный тариф.

7. Определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце.

Строка 1: нет свободных клеток

Строка 2: нет свободных клеток

Строка 3: нет свободных клеток

Столбец 1: нет свободных клеток

Столбец 2: нет свободных клеток

Столбец 3: нет свободных клеток

Столбец 4: нет свободных клеток

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150
    6 50

3

200

A2
    1 150

10
    2 150

1

300

A3

2

3
    3 50
    1 50

100

Потребность

150

150

250

50

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

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является Невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 4*150 + 6*50 + 1*150 + 2*150 + 3*50 + 1*50 = 1550

Целевая функция F=1550

Решаем задачу распределительным методом:

Примем некоторые обозначения:

I - индекс строки;

J - индекс столбца;

M - количество поставщиков;

N - количество потребителей.

I. Определим значения оценок SI, j для всех свободных клеток.

Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус".

S1,1 = c1,1-c1,3+c2,3-c2,1 = 0.

S1,4 = c1,4-c1,3+c3,3-c3,4 = -1.

S2,2 = c2,2-c2,3+c1,3-c1,2 = 10.

S2,4 = c2,4-c2,3+c3,3-c3,4 = 1.

S3,1 = c3,1-c3,3+c2,3-c2,1 = 0.

S3,2 = c3,2-c3,3+c1,3-c1,2 = 2.

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее перспективной является клетка (1,4). Для нее оценка равна -1.

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150

-

    6 50

+

3

200

A2
    1 150

10
    2 150

1

300

A3

2

3

+

    3 50

-

    1 50

100

Потребность

150

150

250

50

Перемещаем по циклу груз величиной в 50 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150

6
    3 50

200

A2
    1 150

10
    2 150

1

300

A3

2

3
    3 100

1

100

Потребность

150

150

250

50

Целевая функция F= 1500

Значение целевой функции изменилось на 50 единиц по сравнению с предыдущим этапом.

II. Опорный план является вырожденным, так как число занятых клеток меньше, чем m+n-1=7.

Сделаем его невырожденным, поместив базисные нули в клетки с координатами (i, j): (2,4)

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150

6
    3 50

200

A2
    1 150

10
    2 150
    1 0

300

A3

2

3
    3 100

1

100

Потребность

150

150

250

50

Определим значения оценок SI, j для всех свободных клеток.

S1,1 = c1,1-c1,4+c2,4-c2,1 = 2.

S1,3 = c1,3-c1,4+c2,4-c2,3 = 2.

S2,2 = c2,2-c2,4+c1,4-c1,2 = 8.

S3,1 = c3,1-c3,3+c2,3-c2,1 = 0.

S3,2 = c3,2-c3,3+c2,3-c2,4+c1,4-c1,2 = 0.

S3,4 = c3,4-c3,3+c2,3-c2,4 = -1.

Наиболее перспективной является клетка (3,4). Для нее оценка равна -1.

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150

6
    3 50

200

A2
    1 150

10

+

    2 150

-

    1 0

300

A3

2

3

-

    3 100

+

1

100

Потребность

150

150

250

50

Перемещаем по циклу груз величиной в 0 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

В результате перемещения по циклу получим новый план:

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150

6
    3 50

200

A2
    1 150

10
    2 150

1

300

A3

2

3
    3 100
    1 0

100

Потребность

150

150

250

50

Целевая функция F= 1500

Аналогично определим значения оценок SI, j для всех свободных клеток.

S1,1 = c1,1-c1,4+c3,4-c3,3+c2,3-c2,1 = 1.

S1,3 = c1,3-c1,4+c3,4-c3,3 = 1.

S2,2 = c2,2-c2,3+c3,3-c3,4+c1,4-c1,2 = 9.

S2,4 = c2,4-c2,3+c3,3-c3,4 = 1.

S3,1 = c3,1-c3,3+c2,3-c2,1 = 0.

S3,2 = c3,2-c3,4+c1,4-c1,2 = 1.

Так как все оценки SI, j>=0, то полученный план является оптимальным.

Транспортная задача решена.

Поставщик

Потребитель

Запасы

Груза

B1

B2

B3

B4

A1

5
    4 150

6
    3 50

200

A2
    1 150

10
    2 150

1

300

A3

2

3
    3 100
    1 0

100

Потребность

150

150

250

50

Минимальные затраты составят: F(x) = 4*150 + 3*50 + 1*50 + 2*250 + 2*100 = 1500

Целевая функция F= 1500

Из 1-го склада необходимо груз направить в 2-й магазин (150), в 4-й магазин (50)

Из 2-го склада необходимо груз направить в 1-й магазин (150), в 3-й магазин (150)

Из 3-го склада необходимо весь груз направить в 1-й магазин

Задача имеет множество оптимальных планов, поскольку оценка для (1;3) равна 0.

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




На какую максимальную величину можно уменьшить запас второго ресурса, не уменьшая дохода - Распределение транспортных ресурсов

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