2015-10-22
367
Если А1>В1, Х11=В1
Запас первого поставщика не употребляется, т.к. запас его исчерпан.
Переходим к распределению груза второго поставщика. Аналогично.
| Поставщик | В1 | В2 | В3 | ai |
| А1 | -- | -- | ||
| А2 | -- | -- | ||
| А3 | ||||
| А4 | -- | -- | ||
| вj |
Метод минимального элемента:
В первую очередь заполняется клетка с минимальным значением тариф. В неё записывается максимально возможное значение поставки, затем из рассмотрения исключается строка, соответствующая поставщику, запасы которого полностью израсходованы или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого снова выбирается клетка с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителя полностью удовлетворён.
В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. В этом случае в свободные клетки надо записать число 0. Условно считаю такую клетку занятой. Число ноль записывается только в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.
|
|
|
Метод Фогеля:
В таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее, в строке или столбце с наибольшей разницей, заполняется клетка с наименьшим тарифом. Строки или столбцы с нулевым остатков в дальнейшем в расчёт не принимаются. На каждом этапе загружается только одна клетка.
Остовное дерево
Пусть жэ это не ориентированный связный граф. Каждый связный подграф ж с чертой принадлежащий жи содержащий все вершины графа жи и не имеющий циклов называется остовом жи или остовным деревом.
Алгоритм прима для нахождения остовного дерева:
Имеется связный граф, каждое ребро которого представлено, в соответствии, не отрицательным числом называемым весом ребра. Необходимо найти оставное дерево минимального веса. Вес дерева равен сумме всех рёбер дерева. В качестве подграфа жи1 из множества жи выбирается граф, вершины которого являются вершинами графа жи, имеющими минимальный вес. На каждом последующем шаге к уже построенному графу добавляется одно ребро.
Шаг К:
Если жи(к-1) из множества жи уже построен, то граф жи (к) из множества жи получается добавление к жи(к-1) ребра л удовлетворяющему следующему условию- к инцидентно какому-нибудь ребру жи(к-1), при добавлении л не образуется цикла, л имеет минимальный вес среди рёбер, удовлетворяющем условиям 1 и 2
