Записать правила построения первого базисного решения замкнутой транспортной задачи по методу северо-западного угла.
Первое базисное допустимое решение легко построить по правилу северо-западного угла. В соответствии с этим правилом, заполнение транспортной таблицы начинается с левой верхней клетки и состоит из однотипных шагов, на каждом из которых из рассмотрения исключается один поставщик или один потребитель:
Построение начинается с верхней левой коетки, в которую мы ставим максимально возможную поставку:
· 
а1<b1 значит x11= min изменённый запрос: bi ʹ=b1-x11
· а1>b1 значит x11= b1 изменённый запас: ai ʹ=a1-x11
· а1=b1 значит x11= b1= a1 изменённый запас: bi ʹ=b1-x11=0
Запомнив х11, мы из дальнейшего рассмотрения первого базисного решения исключаем только одного участника. Во всех случаях после заполнения одной клетки мы исключаем одного участника и переходим к задаче с количеством участников m+n-1 (m-число поставщиков, n - потребителей )
Каждому поставщику ставится в соответствие потенциал pi, а каждому потребителю — потенциал qi. При этом каждой клетке соответствует некоторая оценка: 
.
Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Обычно полагают p1=0. Остальные потенциалы вычисляются из условия, что для базисных клеток ∆ij=0.
Затем вычисляются оценки всех свободных клеток. Если хотя бы одна из оценок строго положительна, то базисное допустимое решение, содержащееся в данной транспортной таблице, не является оптимальным. Выбирается свободная клетка (r, s), соответствующая наибольшей положительной оценке 
.
|
|
|
Для выбранной свободной клетки строится цикл пересчета — замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные — в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы.
Так производится перераспределение поставок вдоль цикла пересчета, при котором происходит такой переход к новому базисному допустимому решению.
Записать правила построения первого базисного решения замкнутой транспортной задачи по методу минимального элемента в матрице тарифов.
При построении первого базисного решения по этому методу первой заполняется клетка с минимальным значением 
(тариф) и в нее заносится максимально возможное значение 
(кол-во груза к перевозке от i-го поставщика j-ому потр-лю). Далее по тем же правилам, что и в методе “северо-западного угла”, исключается один из участников (всегда только 1), находится минимальный из оставшихся элементов и в соответствующую клетку записывается максимально возможное для этой клетки значение . Процесс продолжается до получения базисного решения. При этом заполненными окажутся (m+n-1) клеток.
|
|
|
Замечание. Базисность допустимых решений, получаемых с помощью указанного выше метода,обеспечивается автоматически в случае выполнения следующих рекомендаций:
1)при заполнении очередной клетки необходимо присваивать соответствующей переменной максимально возможное значение;
2)после заполнения очередной клетки исключается из дальнейшего рассмотрения один и только один участник.
Записать математическую модель замкнутой транспортной задачи, составить двойственную к ней задачу и записать условия второй основной теоремы двойственности для получения пары взаимодвойственных задач линейного программирования.
Транспортная задача,в которой суммарные запасы продукции поставщиков = суммарным запросам потребителей, называется сбалансированной, закрытой или замкнутой.В этом случае удовлетворение запросов всех потребителей возможно, если от каждого поставщика вывозится вся продукция , а каждому потребителю продукция доставляется в количестве, соответствующем его запросам. Очевидно,что математической моделью закрытой транспортной задачи будет следующая задача ЛП:
|
|
|
( 1.3);(1,4)
Отметим 2 важных свойства задачи ():
1)задача всегда имеет решение
2)ранг матрицы коэффициентов системы уравнений равен m+n-1.
Дата добавления: 2018-06-01; просмотров: 374; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!