Понятие и содержание транспортной задачи, структура ее ограничений, составление соответствующей матрицы. Существующие методы ее разрешения, история их разработки и анализ эффективности: венгерский, потенциалов. Определение потенциалов текущего плана.
Как одна из задач линейного программирования транспортная задача принципиально может быть решена универсальным методом решения любой задачи линейного программирования, но этот метод не учитывает специфики условий транспортной задачи. В транспортной задаче требуется найти оптимальный план перевозок некоторого продукта от заданного множества производителей, также занумерованных числами , к множеству потребителей, также занумерованных числами . В этих условиях должны быть выполнены балансовые соотношения: Для существования допустимого плана перевозок должен выполнятся общий баланс между спросом и потреблением: При этом транспортную задачу называют сбалансированной. Если предположить, что стоимость перевозки продукта линейно зависит от объема перевозки и характеризуется числами , где - стоимость перевозки единицы продукта от-го производителя к-му потребителю, а - объемы перевозок, то целевая функция в транспортной задаче принимает вид: и задача заключается в минимизации (8) при выполнении ограничений (6) и условия неотрицательности переменных . Для транспортной задачи плотность равна и падает с ростом размерности задачи, что вообще типично для задач линейного программирования.
