Здравствуйте, Елизавета!
Среди задач линейного программирования выделяется класс задач, условия постановки которых в определенной степени позволяют упростить процедуру их решения и определить специфические алгоритмы нахождения этих решений. Этот класс задач получил название "Транспортные задачи".

Рассмотрим постановку таких задач.

Имеется 4 ткацких фабрики, A1, A2,..., A4, которые поставляют ткань на 5 швейных фабрик B1, B2,..., B5.
Известны запасы ткани на каждой ткацкой фабрике в количествах соответственно a1, a2,..., a3 и потребности в ней на каждой швейных фабрике соответственно b1, b2,..., b5.


Пусть, наконец, перевозка единицы продукции из пункта Ai в пункт Bj оценивается величиной cij (cij - заданы).

Необходимо определить наилучший план перевозок по стоимости, т.е. такой план, который давал бы минимальную стоимость перевозок всей произведенной ткани.

Строим математическую модель.

Найти такие xij, которые доставляют минимум линейной форме L, т.е. и удовлетворяют условиям:



Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

Общая схема отдельной итерации такова.

По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj.

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.
Подробный ход решения показан в прикрепленном файле: