n m=
Σ хij = Аi,, Σ хij = Вj,
j=1 i=1
убеждаемся, что все ресурсы распределены и потребители удовлетворены максимальным образом.
Проверяем план на вырожденность: количество заполненных клеток должно быть равно: m + n – 1 = 4 + 3 – 1 = 6.
Считаем стоимость перевозок:
Smin = 15*32 + 6*22 + 4*47 + 5*92 + 9*52 + 12*32 = 1812.
Так как неизвестно, является ли этот план оптимальным, т.е. стоимость перевозок = 1812 ед.ст. или её можно уменьшить, то проверим каждую свободную клетку на оптимальность, а для этого необходимо найти потенциалы U и V, они находятся для заполненных клеток по формуле:
Сij = Ui + Vj, хij > 0.
После чего проверяем свободные клетки на оптимальность по формуле:
Sij = Сij – (Ui + Vj) ≥ 0.
Оказалось, что одна клетка не оптимальна S41 = -6.
Ставим в эту клетку +ρ – это величина для перераспределения ресурсов. От этой клетки строим цикл пересчета – это многоугольник любой конфигурации с прямыми циклами, расположенными в заполненных клетках. По углам этого цикла (прямоугольника) ставим +ρ и –ρ, чтобы был баланс по строкам и столбцам.
Определяем величину перераспределения груза (ресурсов):
ρ = min {32;52} = 32.
Строим новый опорный план:
| Поставщики | Потребители | U | ||
| В1 = 79 | В2 = 74 | В3 = 64 | ||
| А1 = 54 | 15 | 654 | 12 | U1 = 0 |
| А2 = 47 | 447 | 6 | 8 | U2 = -5 |
| А3 = 32 | 24 | 21 | 532 | U3 = -4 |
| А4 = 84 | 1232 | 920 | 1232 | U4 = 3 |
| V | V1 = 9 | V2 = 6 | V3 = 9 | Smin = 1620 |
и весь алгоритм повторяется снова:
Smin2 = 6*54 + 4*47 + 5*32 + 12*32 + 9*20 + 12*32 = 324 + 188 + 160 + 384 +180+ + 384 = 1620.
Все Sij ≥ 0, следовательно 2-й опорный план является оптимальным.
Ответ: минимальная стоимость перевозок равна 1620 ед. стоимости.
Поставки глины: х12 = 54 т; х21 = 47 т; х33 = 32 т; х41 = 32 т; х42 = 20 т; х43 = 32 т.
Список литературы
1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.
2. Архангельский Ю.С., Коваленко И.И. Межотраслевой баланс. – К.: Выща шк. Головное изд-во, 1988.
3. Ашманов С.А. Введение в математическую экономику. – М.: Наука, 1984.
4. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. – М.: Наука, 1980
5. Вивальнюк Л.М. Елементи лінійного програмування. – К.: Вища школа, 1975.
6. Гейл Д. Теория линейных экономических моделей. – М.: ИЛ, 1963.
7. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование (теория, методы и приложения). – М.: Наука, 1969.
8. Данциг Дж. Линейное программирование, его обобщения и приложения. – М.: Прогресс, 1966.
9. Деордица Ю.С., Нефедов Ю.М. Исследование операцій в планировании и управлении. – К.: Вища школа, 1991.
10. Ефимов Н.В. Квадратичные формы и матрицы. – М.: Наука, 1972.
11. Зайченко Ю.П. Исследование операций. – К.: Вища школа, 1979.
12. Исследование операций. / Под ред. Н.С. Кремера. – М.: Бизнес и банки, ЮНИТИ, 1997.
13. Кузнецов Ю.Н. и др. Математическое программирование. – М.: Высшая школа, 1980.
14. Карпелевич Ф.М., Садовский Л.Е. Математическое программми-рование. – И.: Наука, 1967.
15. Лотов А.В. Введение в экономико-математическое моделирование. – М.: Наука, 1984.
16. Математика в экономике: Учебник: в 2-х ч. Ч.1/ А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006.
17. Математические методы и модели в планировании и управлении. Сборник задач. К.: Вища школа, 1985.
18. Терехов Л.Л., Куценко В.А.Ж, Сиднев С.П. Экономико-математические методы и модели в планировании и управлении. – К.: Вища школа, 1984.