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

Имеется 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 ненулевую перевозку (набор базисных переменных)