Постановка задачи. Поиск оптимальных решений

Лабораторная работа №4

Поиск оптимальных решений. Транспортная задача

Краткий комментарий

Транспортная задача

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

Для решения подобного рода задач в линейном программиро­вании существуют специально разработанные методы, а задачи такого рода называются транспортными задачами.

Постановка задачи

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

Исходная информация:

a_i - количество единиц груза в i - м пункте отправления(i = );

b_j - потребность в j - м пункте назначения (j = ), в единицах груза;

c_ij - стоимость перевозки единицы груза из i - го пункта в j - й.

Найти: x_ij – планируемое количество единиц груза для перевозки из i -го пункта отправления в j -й пункт назначения.

Цель: минимум затрат на перевозку.

Математическая модель задачи выглядит следующим образом.

Целевая функция:

→ min.

ЦФ представляет суммарную стоимость перевозок.

Ограничения:

, i= , вывоз груза из i -го пункта отправления равен запасу груза в этом пункте.

, j= доставка груза в j -ый пункт назначения равен спросу на груз в этом пункте.

Граничное условие: , объем перевозимого груза не может быть отрицательным.

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