183892 (Решение задач о планировании перевозок), страница 2
Описание файла
Документ из архива "Решение задач о планировании перевозок", который расположен в категории "". Всё это находится в предмете "экономико-математическое моделирование" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "экономико-математическое моделирование" в общих файлах.
Онлайн просмотр документа "183892"
Текст 2 страницы из документа "183892"
В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.
2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных
, l - свободный индекс
Транспортная задача в матричной постановке и ее свойства
Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (||xi,j||mxn), который минимизирует целевую функцию
на множестве допустимых планов
при соблюдении условия баланса
Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n)mn. Матрицы систем уравнений в ограничениях имеют ранги, равные соответственно m и n. Однако, если, с одной стороны, просуммировать уравнения по m, а с другой — уравнения по n, то получим одно и то же значение. Из этого следует, что одно из уравнений в системе является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n -1, и ее невырожденный базисный план должен содержать m+n -1 ненулевых компонент.
Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц. Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют свободными, а ненулевые — занятыми (xi,j>0).
C1,1 C1,2 …… C1,n
X1,1 X1,2 …… X1,n A1
C2,1 C2,2 …… C2,n
X2,1 X2,2 …… X2,n A2
…. …. …. …. ….
Cm,1 Cm,2 …… Cm,n
Xm,1 Xm,2 …… Xm,n Am
B1 B2 …. Bn
Построение исходного допустимого плана в транспортной задаче
По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей — bj(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аi(0)= аi, bj(0)= bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: хi,j=min{аi(q), bj(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:
аi(q+1)= аi(q) - xi,j, bj(q+1)= bj(q) - xi,j
Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1)= 0 или bj(q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1) = 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.
Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q)=bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.
Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далеко от оптимального. Это происходит потому, что при его построении никак не учитываются значения ci,j. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.
Несбалансированная задача
Если сумма единиц товара поставщиков не равна сумме единиц товара потребителей, то задача не сбалансированная (открытая), иначе задача сбалансированная (закрытая).
В случае, если задача несбалансированная, то добавляем новый пункт перевозок (фиктивных перевозок) поставщика или потребителя, в зависимости от избытка спроса или предложения соответственно. Количество единиц товара нового пункта определяется покрытием избытка спроса или предложения. Данный пункт не должен участвовать в общей стоимости плана перевозок, поэтому стоимость перевозок в/из этого пункта должна быть равна нулю.
Алгоритм метода потенциалов для транспортной задачи
Алгоритм начинается с выбора некоторого допустимого базисного плана (первоначальный план перевозок, составленный, например, методом северо-западного угла). Если данный план не вырожденный, то он содержит m+n-1 ненулевых базисных клеток, и по нему можно так определить потенциалы ui и vj, чтобы для каждой базисной клетки (т. е. для той, в которой xi,j > 0) выполнялось условие vj-ui=ci,j, если xi,j>0
Переменные ui называют потенциалами пунктов производства, a vj — потенциалами пунктов потребления.
Для этого составьте систему для заполненных клеток плана перевозок: vj-ui=ci,j; где ci,j - стоимость перевозки из пункта i в пункт j.
Поскольку система содержит m+n-1 уравнение и m+n неизвестных, то один из потенциалов можно задать произвольно. После этого остальные неизвестные vj и ui - определяются однозначно.
Критерий оптимальности
Для того чтобы допустимый план транспортной задачи xi,j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы ui, vj, для которых
vj-ui=ci,j, если xi,j>0,
vj-ui≤ci,j, если xi,j=0
Вычислите коэффициенты изменения стоимости (dci,j) для незаполненных клеток плана: dci,j = vj - ui - ci,j;
Заметьте: если все dci,j оказались отрицательными, то полученный план оптимальный. Если есть хотя бы один положительный элемент dci,j, то далее ведущей (опорной) клеткой будет клетка [i,j] (при dci,j>0).
Для того чтобы найти новый план перевозок необходимо составить цикл пересчета.
Цикл пересчета представляет собой замкнутую ломаную линию, состоящую из горизонтальных и вертикальных линий, концы которых лежат в заполненных клетках. Ломаная начинается и заканчивается в опорной клетке. Узел в опорной клетке считается положительным, следующий - отрицательный, и так далее чередуясь. Берется минимальное по абсолютной величине значение в отрицательных клетках. Во всех отрицательных клетках это значение отнимается, в положительных прибавляется. Получили новый план перевозок.
Решение задачи
1. Определим модель задачи
b1+b2+b3+b4+b5+b6=230+220+130+170+190+110=1050
a1+a2+a3+a4+a5=240+360+180+120+150=1050
Так как Σai=Σbj, то модель задачи является закрытой.
2. Построим распределительную таблицу по методу северо-западного угла.
V1=8 V2=0 V3=5 V4=2 V5=1 V6=6
230 220 130 170 190 110