Аппроксимация Фогеля: различия между версиями
КУ |
Нет описания правки |
||
Строка 3: | Строка 3: | ||
Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке). |
Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке). |
||
== Пример == |
|||
Используя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в таблице (опорный план этой задачи ранее был найден методом минимального элемента). |
Используя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в таблице (опорный план этой задачи ранее был найден методом минимального элемента). |
||
Строка 47: | Строка 47: | ||
|} |
|} |
||
== Решение == |
|||
Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке |
Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке таблица ниже. |
||
{| class="standard" |
{| class="standard" |
||
|Пункты отправления |
|Пункты отправления |
||
Строка 145: | Строка 145: | ||
|} |
|} |
||
Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце В4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 и будем считать запасы пункта А1 равными |
Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце В4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 и будем считать запасы пункта А1 равными 160—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> |
<math>X = \begin{pmatrix} 0 & 0 & 50 & 110 \\ 120 & 20 &0 & 0 \\ 0 & 30 & 140 & 0 \end{pmatrix}</math> |
||
Строка 155: | Строка 155: | ||
Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным. |
Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным. |
||
==См. также== |
== См. также == |
||
* [[Линейное программирование]] |
* [[Линейное программирование]] |
||
* [[Транспортная задача]] |
* [[Транспортная задача]] |
||
Строка 169: | Строка 169: | ||
|isbn = 5-06-002663-9 |
|isbn = 5-06-002663-9 |
||
}} |
}} |
||
{{rq|img|wikify|topic=math}} |
{{rq|img|wikify|topic=math}} |
||
[[Категория:Численные методы]] |
[[Категория:Численные методы]] |
||
Версия от 22:14, 18 марта 2011
Эта страница предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Викиучебник:К удалению/Март 2011.
Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или немотивированного удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до окончания обсуждения. Администраторам: ссылки сюда, история (последнее изменение), удалить. |
При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).
Пример
Используя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в таблице (опорный план этой задачи ранее был найден методом минимального элемента).
Пункты отправления | Пункты назначения | Запасы | |||
B1 | B2 | B3 | B4 | ||
A1 | 7 | 8 | 1 | 2 | 160 |
A2 | 4 | 5 | 9 | 8 | 140 |
A3 | 9 | 2 | 3 | 6 | 170 |
Потребности | 120 | 50 | 190 | 110 | 470 |
Решение
Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке таблица ниже.
Пункты отправления | Пункты назначения | Запасы | Разности по строкам | ||||||||
B1 | B2 | B3 | B4 | ||||||||
A1 | 7 | 8 | 1 | 2 | 160 | 1 | 6 | - | - | - | - |
A2 | 4 | 5 | 9 | 8 | 140 | 1 | 1 | 1 | 1 | 1 | 0 |
A3 | 9 | 2 | 3 | 6 | 170 | 1 | 1 | 1 | 7 | - | - |
Потребности | 120 | 50 | 190 | 110 | 470 | ||||||
Разности по столбцам | 3 | 3 | 2 | 4 | |||||||
3 | 3 | 2 | - | ||||||||
5 | 3 | 6 | - | ||||||||
5 | 3 | - | - | ||||||||
0 | 0 | - | - | ||||||||
- | 0 | - | - |
Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце В4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 и будем считать запасы пункта А1 равными 160—110=50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке таблицы. Как видно из этой таблицы, наибольшая указанная разность соответствует строке А1. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее с столбцом В3. Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте А1 полностью исчерпаны, а потребности в пункте В3 стали равными 190-50=140 ед. Исключим из рассмотрения строку А1 и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки A3 и столбца B3, строки A3 и столбца B2, строки A2 и столбца B1, строки А2 и столбца B2. В результате получим опорный план:
При этом плане общая стоимость перевозок такова:
S = 1*50 + 2*110 + 4*120 + 5*20 + 2*30 + 3*140 = 1330.
Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным.
См. также
Литература
- Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
Для улучшения этой статьи по математике желательно?:
|