Учебная работа № /7399. «Контрольная Транспортная задача 87
Учебная работа № /7399. «Контрольная Транспортная задача 87
Содержание:
№ 1
Дана транспортная задача в сетевой постановке.
Задача изображена в виде неориентированного связанного графа. На ребрах записаны значения удельных стоимостей , на вершинах
(в кружках) – значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
Выдержка из похожей работы
IIэтап, Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов), Если все небазисные переменные удовлетворяют условию оптимальности, то следует закончить вычисления; в противном случае — перейти к III этапу,
IIIэтап, Выбор выводимой из базиса переменной (используя условия допустимости) из числа переменных текущего базиса; затем нахождение нового базисного решения и возвращение ко II этапу,
Для лучшего понимания метода потенциалов, рассмотрим подробнее все этапы решения транспортной задачи, учитывая ее специфику,
I этап, Определение начального допустимого решения
Для сбалансированной транспортной задачи существует только m + n — 1 независимых уравнений, Таким образом, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных,
Начальное базисное решение транспортной задачи получают непосредственно из транспортной таблицы, Для этого можно использовать три процедуры,
1, Правило «северо-западного угла»
При нахождении опорного плана транспортной задачи методом «северо-западного угла» на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения, Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j), Переменной Х11 приписывают максимальное значение, допускаемое ограничениями на спрос и запасы,
После этого вычеркивают соответствующий столбец или строку, фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными нулю, Если ограничения выполняются одновременно, то можно вычеркнуть либо строку, либо столбец, Процесс завершается тогда, когда будет присвоено значение переменной хmin,
Исходный опорный план, построенный по правилу «северо-западного угла», обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина сij), Более совершенным правилом является правило «минимального элемента»,
2,Правило «минимального элемента»
В методе «северо-западного угла» на каждом шаге потребность первого из оставшихся пунктов назначения удовлетворяется за счет запасов первого из оставшихся пунктов отправления, Очевидно, что выбор пунктов назначения и отправления целесообразно производить, ориентируясь на стоимость перевозок, а именно на каждом шаге следует выбирать какую-либо клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбирать любую из них), и рассматривать пункты назначения и отправления, соответствующие выбранной клетке,
Правило «минимального элемента» заключается в том, чтобы перевозить максимально возможные объемы из пунктов отправления маршрутами минимальной стоимости, Заполнение таблицы начинаем с клетки, которой соответствует наименьшая стоимость перевозки (элемент cij) из всей таблицы, Переменной этой клетки хij присваивается максимально возможное значение с учетом ограничений, Затем остаток по столбцу или строке помещается в клетку того же столбца или строки, которой соответствует следующее по величине значение сij и т, д, Иными словами, последовательность заполнения клеток определяется по величине сij, а помещаемая в этих клетках величина хij такая же, как и в правиле «северо-западного угла»,
3″
