Экономико-математическая модель. ТЗ

Транспортные задачи(ТЗ)- частный случай задачи линейного программирования.

В ТЗ существуют поставщики и потребители грузов. У каждого поставщика имеется определенное количество груза - мощность поставщика, а каждому потребителю нужно определенное количество груза - спрос потребителя. Известны затраты на перевозку единицы груза. Нужно составить такой план перевозок, при котором: 1) Суммарные затраты на перевозку груза будут минимальными;2) По возможности будут задействованы все мощности поставщиков; 3)По возможности будет удален весь спрос потребителей.

Закрытая модель ТЗ(сбалансированная модель ТЗ)- модель, в которой суммарная мощность поставщиков равна суммарному спросу потребителей.

Открытая модель ТЗ(не сбалансированная модель ТЗ) – модель, в которой суммарная мощность поставщиков не равна суммарному спросу потребителей.

В процессе решения открытая модель всегда сводится к закрытой. Поэтому сначала рассмотрим закрытую модель.

Алгоритм решения закрытой модели/ТЗ:

1) Составляется специальная таблица поставщиков и потребителей с указанием их мощностей и спросов;

2) Находим первоначальный план поставок:

-метод северо-западного угла;

-метод минимальной стоимости;

-метод потенциалов;

3) Оптимизируем план распределительным методом;

Задача2.1

Требуется построить экономико-математическую модель следующей задачи. Имеется 3 поставщика и 4 потребителя. Мощности поставщиков и спрос потребителей, а также затраты на перевозку единицы груза для каждой пары поставщик- потребитель сведены в таблицу поставок:

 

Таблица 2.1

Поставщик	Мощность поставщика	Потребители и их спрос
		X11	X12	X13	X14
		X21	X22	X23	X24
		X31	X32	X33	X34

i-номер строки;

j-номер столбца;

ij-клетка;

В клетке отмечены коэффициенты затрат-затраты от i-го поставщика к j-му потребителю.

 

Решение:

Построим экономико-математическую модель. Искомый объем i-го поставщика j-ому потребителю есть X_ij. Назовем поставкой клетки(ij).

Запишем уравнения баланса для каждой строки таблицы поставок:

X₁₁ + X₁₂ + X₁₃ + X₁₄ =60;

X₂₁ + X₂₂ + X₂₃ + X₂₄ =120;

X₃₁ + X₃₂ + X₃₃ + X₃₄ =100;

 

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

X₁₁ + X₂₁ + X₃₁ =20;

X₁₂ + X₂₂ + X₃₂ =110;

X₁₃ + X₂₃ + X₃₃ =40;

X₁₄ + X₂₄ + X₃₄ =110;

 

Суммарные затраты F на перевозку выражается через коэффициенты затрат (в углах ячеек):

 

F= X₁₁ + 2X₁₂ + 3X₁₄ +X₂₁ +6 X₂₂ + 5X₂₃ +2X₂₄ + 6X₃₁ +3X₃₂+7X₃₃ + 4X₃₄ ;

 

Особенности экономико –математической модели:

Система ограничений – система уравнений в канонической форме. Коэффициенты при переменных равны 0 или 1. Каждая из переменных входит в систему ограничений два раза.

Обозначения:

C_ij – коэффициенты затрат.

M_i – мощность поставщиков.

N_j –спрос потребителей.

i – 1,2,3…,m;

j – 1,2,3…,n;

m – число поставщиков.

n – число потребителей.

n

Тогда ∑ X_ij= M_i i=1,2,…,m(2.1)

J=1

 

 

m

Тогда ∑ X_ij= N_j j=1,2,…,n(2.2)

i=1

 

Целевая функция в общем виде;

 

n m

F= ∑ ∑ C_ij x_ij –> min; (2.3)

J=1 i=1

 

n

∑ x_ij= N_j ;

J=1 - система ограничений.

n

∑ x_ij= M_i;

i=1

 

При данных ограничениях данная целевая функция должна стремиться к минимуму.

Математическая формулировка:

* * * *

На множестве решений системы ограничений (2.1, 2.2) найти такое решение, X(x₁₁, x₁₂,…,x_mn) , при котором значение целевой функции F будет минимально. Являясь задачей линейного программирования ТЗ может быть решена симплексным методом. Однако специфичная форма системы ограничений, позволяет упростить этот метод. Существуют разные методы нахождения оптимального решения;

-метод северно-западного угла;

-метод минимальной стоимости;

-метод потенциалов;