Общая постановка производственно-транспортной задачи

 

Обозначим через х_ij количество тонн груза, предназначенного к отправке из пункта А_i в пункт В_j. Тогда количество груза, планируемое к доставке в пункт В_j из всех пунктов отправления, составит

 

х_1j + х_2j +…+ x_mj = Х_ij . (1)

 

Так как потребность пункта назначения В_j составляет b_j, то при планировании перевозок должно соблюдаться равенство

 

X_ij = b_j .

 

Сказанное справедливо для  любого пункта В_j. Поэтому получаем n уравнений

х ₁₁ + х ₂₁ +…+ х _m1 = b ₁

х ₁₂+ х ₂₂ +…+ х_m2 = b ₂

….……………………… (2)

х _1n + х _2n+…+ х _mn = b _n

 

С другой стороны, общее количество груза, отправляемого из пункта А_i во все пункты назначения В_j составит

 

х_i1+х_i2+...+x_in= Х _ij.  (3)

 

По условиям задачи эта  сумма должна быть равна количеству груза в пункте =А_i,т.е.

Х _ij=a_i .

 

Так как приведённое рассуждение  относится к любому пункту отправления, имеем m уравнений

 

х ₁₁ + х ₂₁ +…+ х _1n = a ₁

х ₂₁+ х ₂₂ +…+ х_2n = a ₂

……………………. (4)

х _m1 + х _m2+…+ х _mn = a _m

 

Более компактно уравнения (1.1) - (1.4) можно записать следующим  образом:

Х _ij= b_j, j = 1, 2, …, n; (5)

Х _ij= a_i, i = 1, 2, …, m; (6)

P = 1₁₁x₁₁ +1₁₂ x₁₂+…+1_ij x_ij +…+1_mn x_mn = l_ij X _ij. (7)

 

Очевидно, что объем каждой поставки не может быть отрицательным  числом, т.е.

 

x_ij >0, i=1,2, ..., m;  j=1,2,..., n. (8)

 

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

 

l_ij X _ij, j = 1, 2, …, n, i = 1, 2, …, m  (9)

 

при условиях

X _ij= b_j, j = 1, 2, …, n; (10)

X_ij= a_i, i = 1, 2, …, m; (11)

x_ij>0, i =1, 2, ..., m; j=1, 2,..., n. (12)

 

Соблюдение равенства (1.10) обеспечивает полное удовлетворение запросов всех потребителей. Уравнения (1.11) гарантируют  полный вывоз из пунктов отправления, а уравнения (1.9) - неотрицательность  переменных. Для совместности системы  уравнений (1.9 - 1.12) необходимо, чтобы

 

a_i = b_j . (13)

 

Равенство (1.13) является не только необходимым, но и достаточным условием для совместности системы уравнений (1.9 – 1.12).

Поскольку уравнения (1.10 - 1.12) содержат неизвестные только в первой степени, а показатель L_ij в формуле (1.9) не зависит от x_ij, сформулированная задача является задачей линейного программирования. Формулировка задачи, в которой спрос и предложение равны, получила название закрытой модели.

Модель транспортной задачи имеет следующие особенности:

1. Модель выражается неопределённой  системой линейных уравнений  и, следовательно, имеет бесчисленное  множество возможных решений.

2. Модель совместна, т.е.  имеет решение.

3. Элементами матрицы  системы являются единицы и  нули.

4. Система является линейно-зависимой,  так как любое её уравнение  можно представить в виде линейной  комбинации остальных уравнений.

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

6. Целевая функция выражается  линейной формой. Матрица целевой  функции — это матрица-строка, элементами которой могут быть  расстояния, время или стоимость  перевозки.

Для решения транспортной задачи разработаны специальные  методы, позволяющие из бесчисленного  множества решений найти оптимальное. Одним из таких методов является распределительный, имеющий несколько  разновидностей, которые отличаются в основном способом выявления оптимального решения. Общая схема метода следующая. Вначале составляют допустимый исходный план задачи, который затем исследуется  на оптимальность. Если при проверке окажется, что составленный план оптимален, то решение закончено. В противном  случае при помощи специального приёма осуществляется переход к новому, лучшему плану. Этот план снова исследуется  на оптимальность и в случае неоптимальности  опять улучшается. Указанный процесс  вычислений повторяется до получения  оптимального решения.

Разновидности распределительного метода отличаются в основном способом выявления оптимального решения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 2009.

2. Вентцель Е.С. Исследование операций. – М.: Наука, 2007

3. Горелик В.А., Ушаков И.А. Исследование операций. – М: Машиностроение, 2010. – 286 с.

4. Давыдов Э.Т. Исследование операций: Учебное пособие для студентов вузов. – М.: Высшая школа, 2008. – 383 с.

5. Ермолаев Ю.М. Математические методы исследования операций. – К.: Наука, 2005.

6. Костина Г.П. Коммерческая логистика: Учеб. пособие / Г.П. Костина – 2-я ред. – М.: Доброе слово, 2007

7. Кузнецов Ю.Н. Математическое программирование. – М.: Наука, 2008.

8. Михайлов Ю.И., Федорков А.И. Границы конкуренции логистических систем / Экономика и менеджмент на предприятиях химической промышленности: сборник научных трудов/ Под ред. М.Л.Колесова.-СПбГИЭА.-СПб.-1998.-128 с.-С.74-78.

9. Таха Х. Введение в исследование операций. – м.: Мир, 2003.

10. Толбатов Ю.А. Эконометрика в Excel. – К.: Четверта хвиля, 2011.