3. Транспортная задача

3.1 Описание задачи

Имеется n пунктов отправления (складов), на каждом из которых размещено a_i единиц товара. Этот товар должен быть доставлен m потребителям в количестве b_j каждому. Общее количество запасов равно суммарной потребности в товаре (сбалансированная задача)

Стоимость перевозки товара из i–го склада j–му потребителю равна c_ij, а количество товара, перевезенного из i–го склада j–му потребителю равна x_ij (перевозка). Нужно составить такой план перевозок, чтобы все заявки были удовлетворены, и при этом чтобы суммарная стоимость перевозок была минимальна

Очевидно, решение должно удовлетворять условиям баланса на каждом складе и у каждого потребителя и условию неотрицательности переменных (перевозок)

У нас n+m ограничений, связанных условием сбалансированности, т.е. n+m–1-но независимое ограничение-равенство. Значит допустимый опорный план (вершина) – это n+m–1 базисных (ненулевых) переменных, все остальные равны нулю.

В отличие от симплекс-метода, при построении матрицы транспортной задачи каждой переменной x_ij отвечает не столбец матрицы, а одна ячейка. При этом строка отвечает одному складу, а столбец – одному потребителю.

Матрица задачи содержит n строк и m столбцов, каждый элемент матрицы (переменная x_ij) есть перевозка с i-го склада j-ому потребителю.

3.2 Построение допустимого опорного плана (вершины) методом северо-западного угла

Идея метода состоит в том, что заявку каждого потребителя, начиная слева, нужно удовлетворить за счет поставщиков с как можно меньшими номерами. Т.е. самому левому потребителю – от самого верхнего поставщика. В большинстве случаев такой принцип позволяет построить допустимый опорный план – т.е. план перевозок, содержащий ровно n+m–1 ненулевую перевозку (набор базисных переменных)

3.3 Циклы как метод перехода к лучшей вершине

Циклом называется замкнутая ломанная, соединяющая несколько выбранных клеток(перевозок x_ij), которая в каждой выбранной клетке поворачивает на 90. Вершины цикла (выбранные клетки) помечаются знаками «+» и «–», причем знаки всегда строго чередуются, т.е. всегда соседние по ходу цикла вершины помечены разными знаками. Перенести k единиц груза по циклу означает в положительных вершинах увеличить x_ij на k единиц, а в отрицательных вершинах уменьшить x_ij на k единиц. Поскольку цикл помечен таким образом, что в каждой строке и каждом столбце количество плюсов и минусов одинаково, переброска груза по циклу не нарушает условий баланса. Цена цикла равна сумме цен помеченных ячеек (с учетом знака) на величину переброски k.

Цикл всегда строится таким образом, что он начинается в пустой ячейке, которая помечается знаком «+» а все остальные вершины цикла находятся в заполненных ячейках (базисные переменные). Если реализация цикла приводит к уменьшению цены перевозок, то нам выгодно переместить по циклу максимально большое количество груза, чтобы достичь максимального эффекта. Ограничением на эту величину является самая малая из тех базисных переменных, которые помечены знаком «–». Если попытаться переместить больше, то в этой ячейке x_ij станет отрицательным, но если переместить ровно столько, сколько есть в самой «малой» ячейке, помеченной минусом, то в итоге в этой ячейке x_ij станет нулем. Т.е. мы одну небазисную переменную сделали базисной (положительной) а одну базисную небазисной (нулевой). Количество базисных ячеек не изменилось – значит мы из одной вершины перешли в другую вершину