Лабораторная работа (стр. 12 ) | Авторская платформа Pandia.ru

Докажем это предложение.

Теорема об оптимальном плане ТЗ.

Если для всех базисных клеток плана , а для всех свободных клеток , то план является оптимальным.

Доказательство.

Обозначим - план с соответствующей ему системой платежей , обладающий свойством оптимальности. Определим стоимость этого плана:

Теперь попробуем изменить план .

Стоимость нового плана:

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

Таким образом доказано, что признаком оптимальности плана является выполнение двух условий:

План, обладающий таким свойством, называется потенциальным, а соответствующие ему платежи - потенциалами пунктов и . Оптимальный план можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющих условию (а). Затем улучшим план, одновременно меняя систему платежей так, чтобы они приближались к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей:

Для любой системы платежей , удовлетворяющей условию (а), каждая свободная клетка имеет цену цикла, равную разности стоимости и псевдостоимости в этой клетке:

Итак, можно предположить следующий алгоритм решения ТЗ методом потенциалов.

1. Взять любой опорный план перевозок, в котором отмечены базисных клеток.

2. Определить для этого плана платежи исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям:

НЕ нашли? Не то? Что вы ищете?

Один из платежей можно назначить произвольно, например, положить равным 0, т. к. уравнений всего , а число неизвестных .

3. Подсчитать псевдостоимости для всех свободных клеток. Если окажется, что , то план оптимален.

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

5. Перейдем к пункту 2.

Понятиям платежей и псевдостоимостей можно дать следующую интерпретацию: пусть поставщики и потребители действуют как единая экономическая система, а платежи - реальные платежи, которые пункты и платят за перевозку единицы груза «перевозчику». Перевозки единицы груза из пункт в пункт объективно стоит , а стороны А и В вместе платят за эту перевозку .