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

Транспортная задача - это модель ситуации, в которой требуется найти оптимальный план перевозки некот. груза из конечного числа пунктов отправления с заданными объемами производства в конечное число пунктов назначения с требуемыми объемами потребностей при известных затратах на перевозку единицы груза между каждой парой пунктов поставки и потребления. Удельные затраты не зависят от количества перевозимого груза. Здесь под оптимальным понимается план, минимизирующий суммарные затраты на перевозки. Пример: задача с двумя пунктами отправления и тремя пунктами назначения. а ₁ и а ₂ – количество груза, которым располагают пункты отправления, b ₁, b ₂, b ₃ – потребности в грузе пунктов назначения.

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

Пункты	B1	B2	B3	Кол-во груза
A1	С 11 Х 11	С 12 Х 12	С 13 Х 13	a 1
A2	С 21 Х 21	С 22 Х 22	С 23 Х 23	a 2
Потр-ть	b 1	b 2	b 3

Обозначения: xij - количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения; Сij – затраты на перевозку единицы груза из i-го пункта отправления в j-й пункт назначения, получим таблицу

Необходимо минимизировать суммарные затраты по перевозке, целевая функция запишется в виде L=C ₁₁ x ₁₁ + C ₁₂ x ₁₂ + C ₁₃ x ₁₃+ C ₂₁ x ₂₁ + C ₂₂ x ₂₂ + C ₂₃ x ₂₃ →;min.

Каждый ПН должен получить треб. количество груза. B₁: x ₁₁ +x ₂₁ =b ₁; B₂: x ₁₂ +x ₂₂ =b ₂; B₃: x ₁₃ +x ₂₃ =b ₃.

Поскольку задача сбалансированная, весь груз из ПО дб вывезен. Это требование отражается в модели двумя равенствами: А₁: х ₁₁ +х ₁₂ +х ₁₃ =а ₁; А₂: х ₂₁ +х ₂₂ +х ₂₃ =а ₂.

Наконец, физический смысл переменных накладывает на них ограничение неотрицательности

" x_ij³0.

В результате мы получили модель транспортной задачи, содержащей только линейные функции. Очевидно, что характер модели не изменится при увеличении числа пунктов.