183500 (584635), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Для клетки A₄B₂ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(50, 130, 90)=50.

Переходим к следующей итерации.

Стоимость 3 плана перевозки:

z₃ = 80 · 9+140 · 4+120 · 5+150 · 3+50 · 0+140 · 0+40 · 0 = 2330.

Для базисных клеток система потенциалов такая:

a₁+b₁=9; a₁+b₄=4;

a₂+b₁=5;

a₃+b₂=3;

a₄+b₂=0; a₄+b₃=0; a₄+b₄=0.

Поскольку количество переменных меньше, чем уравнений, то положим: a₁=0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁+b₂=0+4=4 ≤ 8; a₁+b₃=0+4=4 ≤ 7;

a₂+b₂=–4+4=0 ≤ 6; a₂+b₃=–4+4=0 ≤ 10; a₂+b₄=–4+4=0 ≤ 3;

a₃+b₁=–1+9=8 > 2 [6]; a₃+b₃=–1+4=3 ≤ 5; a₃+b₄=–1+4=3 ≤ 7;

a₄+b₁=–4+9=5 > 0 [5];

Для клетки A₃B₁ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(80, 40, 150)=40.

Переходим к следующей итерации.

Стоимость 4 плана перевозки:

z₄ = 40 · 9+180 · 4+120 · 5+40 · 2+110 · 3+90 · 0+140 · 0 = 2090.

Для базисных клеток система потенциалов такая:

a₁+b₁=9; a₁+b₄=4;

a₂+b₁=5;

a₃+b₁=2; a₃+b₂=3;

a₄+b₂=0; a₄+b₃=0;

Поскольку количество переменных меньше, чем уравнений, то положим: a₁=0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁+b₂=0+10=10 > 8 [2]; a₁+b₃=0+10=10 > 7 [3];

a₂+b₂=–4+10=6 ≤ 6; a₂+b₃=–4+10=6 ≤ 10; a₂+b₄=–4+4=0 ≤ 3;

a₃+b₃=–7+10=3 ≤ 5; a₃+b₄=–7+4=–3 ≤ 7;

a₄+b₁=–10+9=–1 ≤ 0; a₄+b₄=–10+4=–6 ≤ 0;

Для клетки A₁B₃ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(40, 110, 140)=40.

Переходим к следующей итерации.

Стоимость 5 плана перевозки:

z₅ = 40 · 7+180 · 4+120 · 5+80 · 2+70 · 3+130 · 0+100 · 0 = 1970.

Для базисных клеток система потенциалов такая:

a₁+b₃=7; a₁+b₄=4;

a₂+b₁=5;

a₃+b₁=2; a₃+b₂=3;

a₄+b₂=0; a₄+b₃=0;

Поскольку количество переменных меньше, чем уравнений, то положим: a₁=0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁+b₁=0+6=6 ≤ 9; a₁+b₂=0+7=7 ≤ 8;

a₂+b₂=–1+7=6 ≤ 6; a₂+b₃=–1+7=6 ≤ 10; a₂+b₄=–1+4=3 ≤ 3;

a₃+b₃=–4+7=3 ≤ 5; a₃+b₄=–4+4=0 ≤ 7;

a₄+b₁=–7+6=–1 ≤ 0; a₄+b₄=–7+4=–3 ≤ 0;

Условие оптимальности выполняется для всех клеток, следовательно последний план является оптимальным. Его стоимость составляет 1970 у.е. Следует заметить, что потребители не дополучат 230 ед. груза.

2) Метод минимальной стоимости

Найдем опорный план методом минимальной стоимости [1, c. 142].

Стоимость начального плана перевозки:

z₀ = 40 · 7+180 · 4+120 · 5+80 · 2+70 · 3+130 · 0+100 · 0 = 1970.

Для базисных клеток система потенциалов такая:

a₁+b₃=7; a₁+b₄=4;

a₂+b₁=5;

a₃+b₁=2; a₃+b₂=3;

a₄+b₂=0; a₄+b₃=0;

Поскольку количество переменных меньше, чем уравнений, то положим: a₁=0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁+b₁=0+6=6 ≤ 9; a₁+b₂=0+7=7 ≤ 8;

a₂+b₂=–1+7=6 ≤ 6; a₂+b₃=–1+7=6 ≤ 10; a₂+b₄=–1+4=3 ≤ 3;

a₃+b₃=–4+7=3 ≤ 5; a₃+b₄=–4+4=0 ≤ 7;

a₄+b₁=–7+6=–1 ≤ 0; a₄+b₄=–7+4=–3 ≤ 0;

Условие оптимальности выполняется для всех клеток, следовательно последний план является оптимальным. Его стоимость составляет 1970 у.е. Следует заметить, что потребители не дополучат 230 ед. груза.

Также отмечаем совпадение решений двумя методами.

Ответ: 1970.

Література

1. Акулич И. Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. – 319 с.

2. Костевич Л. С. Математическое программирование. Мн.: Новое знание, 2003. – 424 с.

Характеристики

Список файлов ответов (шпаргалок)