Аппроксимация Фогеля: различия между версиями

Нет описания правки
(КУ)
Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).
 
===== Пример: =====
Используя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в таблице (опорный план этой задачи ранее был найден методом минимального элемента).
 
|}
 
===== Решение =====
Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке таблица ниже.
{| class="standard"
|Пункты отправления
|}
 
Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце В4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 и будем считать запасы пункта А1 равными 160-110160—110=50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке таблицы. Как видно из этой таблицы, наибольшая указанная разность соответствует строке А1. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее с столбцом В3. Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте А1 полностью исчерпаны, а потребности в пункте В3 стали равными 190-50=140 ед. Исключим из рассмотрения строку А1 и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки A3 и столбца B3, строки A3 и столбца B2, строки A2 и столбца B1, строки А2 и столбца B2. В результате получим опорный план:
 
<math>X = \begin{pmatrix} 0 & 0 & 50 & 110 \\ 120 & 20 &0 & 0 \\ 0 & 30 & 140 & 0 \end{pmatrix}</math>
Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным.
 
== См. также ==
* [[Линейное программирование]]
* [[Транспортная задача]]
|isbn = 5-06-002663-9
}}
 
{{rq|img|wikify|topic=math}}
 
[[Категория:Численные методы]]
 
Анонимный участник