Учебная работа № 88681. «Контрольная Транспортная задача. Вариант 15, задача 4

Выдержка из похожей работы

ru/

1, Понятие транспортной задачи

Построение экономическо-математической модели состоит в создании упрощенной математической модели, в которой в схематичной форме отражена структура изучаемого процесса, При этом особое внимание должно быть уделено отражении в модели всех существенных особенностей задачи и учет всех ограничивающих условий, которые могут повлиять на результат, Затем определяется цель решения, выбирается критерий оптимальности и дают математическую формулировку задачи,

Задачи транспортного типа широко распространены в практике, Кроме того, к ним сводятся многие другие задачи линейного программирования — задачи о назначениях, сетевые, календарного планирования,

Как одна из задач линейного программирования транспортная задача принципиально может быть решена универсальным методом решения любой задачи линейного программирования, но этот метод не учитывает специфики условий транспортной задачи, Поэтому решение ее симплекс-методом оказывается слишком громоздким,

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

В транспортной задаче требуется найти оптимальный план перевозок некоторого продукта от заданного множества производителей, также занумерованных числами , к множеству потребителей, также занумерованных числами ,

Производственные возможности -го производителя заданы объемом производимого продукта — , Спрос -го потребителя на этот продукт задается числом ,

Обозначим планируемый объем перевозок от -го производителя к -ому потребителю как , В этих условиях должны быть выполнены балансовые соотношения:

Для существования допустимого плана перевозок должен выполнятся общий баланс между спросом и потреблением:

При этом транспортную задачу называют сбалансированной,

Можно убедиться, например, что в сбалансированной транспортной задаче

являются допустимым вариантом перевозок, то есть удовлетворяющим ограничениям (6),

Целью решения транспортной задачи является минимизация суммарных транспортных расходов, Если предположить, что стоимость перевозки продукта линейно зависит от объема перевозки и характеризуется числами , где — стоимость перевозки единицы продукта от -го производителя к -му потребителю, а — объемы перевозок, то целевая функция в транспортной задаче принимает вид:

и задача заключается в минимизации (8) при выполнении ограничений (6) и условия неотрицательности переменных ,

Переменные можно представить в виде матрицы (см, табл, 1),

Таблица: Матрица объемов перевозок,

Потребители

Поставщики

1

2

…

1

…

2

…

…

…

…

…

…

M

…

или, более традиционную, в виде вектора развернув в этот вектор вышеприведенную таблицу, При естественном обходе таблицы (1) (скажем по столбцам) матрица ограничений (6) примет специфический вид, приведенный в табл, 2,

Матрица ограничений транспортной задачи

1

1

…

1

1

1

…

1

…

1

1

…

1

1

1

…

1

1

1

…

1

…

1

1

…

1

Видно, что матрица ограничений транспортной задачи обладает рядом характерных особенностей, из которых отметим следующие:

— большая часть ее элементов равна нулю,

— среди ненулевых элементов много одинаковых»