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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок туристов из m пунктов отправления A₁, A₂,.., A_m (аэропорты Турции и Египта) в n пунктов назначенияB₁, B₂,.., B_n (аэропорты Москвы). Известны удельные затраты на доставку одного туриста из каждого пункта отправления в каждый пункт назначения. Количество туристов в аэропортах Турции и Египта ограничено. Так же известно максимальное число пассажиров, которых может принять Москва. Необходимо организовать их перелет так, что бы затраты были минимальными.

Введём обозначения заданных параметров:

j – индекс потребителей, j = 1…n;

i – индекс поставщиков, i = 1…m;

Аi – объём имеющейся продукции i-го поставщика;

Вj – объём потребности в продукции j-го потребителя;

cij – удельные затраты на перевозку единицы продукции от i -го поставщика;

j-му потребителю.

Введём неизвестные переменные:

хij – планируемый объём перевозки продукции от i-го поставщика j-му потребителю.

В терминах введённых обозначений данная задача запишется следующим образом.

(2.1)

От каждого поставщика можно вывести объём продукции не более имеющегося количества:

(2.2)

Потребность каждого потребителя в продукции должна быть удовлетворена:

(2.3)

Условие не отрицательности:

(2.4)

Математическую модель часто удобно записывать в свёрнутом виде.

; (2.5)

; (2.6)

; (2.7)

; (2.8)

Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице1:

1) Введем переменные задачи (матрицу перевозок):

2) Запишем матрицу стоимости:

3) Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

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

4) Составим систему ограничений задачи.

Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:

Это означает, что запасы поставщиков вывозятся полностью.

Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:

Это означает, что запросы потребителей удовлетворяются полностью.

Необходимо также учитывать, что перевозки не могут быть отрицательными:

;

5) Таким образом, математическая модель рассматриваемой задачи записывается следующим образом:

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

;

;