Требуется перегнать автомобили с трех заводов в четыре торговых центра. Время, необходимое для перегонки каждого автомобиля, объемы поставок и потребности приведены в таблице. Как найти план поставки, минимизирующий суммарные расходы на перевозку при удельных затратах 10 € в час? Изменится ли модель, если решают задачу скорейшего исполнения заказа при одновременной отправке всех машин?

Требуется перегнать автомобили с трех заводов в четыре торговых центра. Время, необходимое для перегонки каждого автомобиля, объемы поставок и потребности приведены в таблице. Как найти план поставки, минимизирующий суммарные расходы на перевозку при удельных затратах 10 € в час? Изменится ли модель, если решают задачу скорейшего исполнения заказа при одновременной отправке всех машин?

Заводы Торговые центры Объемы поставок

Север Юг Востоксток Запад
ГАЗ 7,0 3,8 2,4 9,2 14
КамАЗ 5,8 1,8 5,6 7,2 20
ЗиЛ 1,9 1,0 10,0 3,0 26
Размеры заказов 16 11 15 18

Решение.
Задачу будем решаеть в следующем порядке. Нахом начальное опорное решение. Определяем значение целевой функции

Все свободные клетки, которым соответствуют значения tij > Т, исключаем из рассмотрения (перечеркиваем). Занимать эти клетки нецелесообразно, так как увеличится. Чтобы уменьшить значение целевой функции, необходимо освободить клетку, в которой tij достигает максимума. Для этого строим разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки, расставляем поочередно знаки «+» и «-» и осуществляем сдвиг на величину min {xij}. Если удается эту клет у разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение, на котором значение целевой функции меньше, чем на предыдущем. Далее снова пытаемся разгрузить клетку, соответствующую Т. Описанную процедуру продолжаем до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.
Для матрицы, заданной в условии задачи построим первоначальный план перевозок по методу минимальной стоимости.

Читайте также:  Рассчитайте: - средний размер страховых выплат; - моду и медиану.

16 11 15 18
14 7,0

3,8

2,4
2 9,2
12
20 5,8
1 1,8

5,6
13 7,2
6
26 1,9
15 1,0
11 10,0

3,0

Максимум целевой функции: Т=9,2. Клетку (3, 3) вычеркиваем. Для клетки (1,3) строим разгрузочный цикл (1,2) → (1,4) → (2,4) → (2,2) → (1,2). Получаем:

16 11 15 18
14 7,0

3,8
11 2,4
2 9,2
1
20 5,8
1 1,8

5,6
13 7,2
6
26 1,9
15 1,0

10,0

3,0
11

Максимум целевой функции: Т=9,2. Для клетки (1,1) строим разгрузочный цикл (1,1) → (1,4) → (3,4) → (3,2) → (1,2). Получаем:

16 11 15 18
14 7,0
1 3,8
11 2,4
2 9,2

20 5,8
1 1,8

5,6
13 7,2
6
26 1,9
14 1,0

10,0

3,0
12

Максимум целевой функции: Т= 7,2. Клетку (1, 4) вычеркиваем. Для клетки (2,2) строим разгрузочный цикл (2,2) → (2,4) → (3,4) → (3,1) → (2,1) → (2,2). Получем:

16 11 15 18
14 7,0
7 3,8
5 2,4
2 9,2

20 5,8
1 1,8
6 5,6
13 7,2

Читайте также:  Решить смешанную задачу для однородного уравнения методом разделения переменных utt=a2uxx.

26 1,9
8 1,0

10,0

3,0
18

Максимум целевой функции: Т= 7,0. Клетку (1, 4) вычеркиваем. Для клетки (2,2) строим разгрузочный цикл (2,2) → (2,4) → (3,4) → (3,1→ (1,2) → (2,2)). Получем:

16 11 15 18
14 7,0

3,8
5 2,4
9 9,2

20 5,8
8 1,8
6 5,6
6 7,2

26 1,9
8 1,0

10,0

3,0
18

Максимум целевой функции: Т= 5,8. С помощью оставшихся невычеркнутых клеток разгрузить клетку (2, 1) не удается, поэтому Т =5,8 является оптимальным решением.
Ответ: Т =5,8.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...