Транспортная задача. 
Линейное программирование распределения ресурсов

ПОСТАНОВКА ЗАДАЧИ

Три издательства с объемами запасов продукции 40, 50 и 20 единиц соответственно получили заявки от четырех сотрудничающих с ними книжных магазинов на поставку книг в количестве 20, 30, 30 и 30 единиц соответственно. В таблице указаны стоимости перевозки единицы продукции из i-го пункта отправления в j-й пункт назначения. Вводятся переменные, определяющие количество отправляемых грузов из i-го издательства в j-й книжный магазин потребления, — x_ij

Ставится задача минимизировать стоимость перевозок, поэтому целевая функция будет.

.

Количество груза, отправляемого с каждого склада, не должно превышать имеющихся запасов:

.

Условие выполнения заявок каждого пункта потребления запишется в виде.

.

ОПРЕДЕЛЕНИЕ ДОПУСТИМОГО БАЗИСНОГО РЕШЕНИЯ

Составим матрицу перевозок, указав запасы пунктов отправления и потребности (заявки) пунктов назначения. A₁, …, A_i, …, A_m — обозначения пунктов отправления, B₁,…, B_j,…, B_n — обозначения пунктов назначения.

Используем для нахождения допустимого базисного решения диагональный метод (метод северо-западного угла), начиная заполнение матрицы с угловых объектов, удовлетворяя потребность пункта В₁ запасами пункта А₁.

Таким образом, получим для решения задач возможные допустимые значения базисных переменных х₁₁=20, х₁₂=10, х₂₂=10, х₂₃=30, х₂₄=10, х₃₄=20. Общая стоимость перевозок F=400. Это и есть допустимое базисное решение.