Основы математического программирования (стр. 13 )

· вектора запасов поставщиков А = (а1, а2, …, аm)

· вектора запросов потребителей В = (b1, b2, …, bn)

· матрицы стоимостей

C =	c11 с12 … с1n c21 с22 … с2n … … … … cm1 сm2 … сmn

В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и с/х предприятия, заводы, фабрики, склады, магазины и т. п.

Однородными считаются грузы, которые могут быть перевезены одним видом транспорта.

Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т. п.

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

Переменными (неизвестными) транспортной задачи являются xij i = 1, 2, …, m, j = 1, 2, …, n – объемы перевозок от каждого i-ого поставщика каждому j-му потребителю.

Так как произведение cijxij определяет затраты на перевозку груза от i-ого поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

m n

∑ ∑cijxij

i=1 j=1

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

m n

Z(x) = ∑ ∑cijxij min

i=1 j=1

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

Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью

n

∑ xij = ai, i=1, 2, …, m

j=1

Вторая группа их n уравнений выражает требования полностью удовлетворить запросы всех n потребителей

m

∑ xij = bj, j=1, 2, …, n

i=1

Учитывая условие неотрицательности объемов перевозок, математическую модель можно записать так:

m n

Z(x) = ∑ ∑cijxij min (1)

i=1 j=1

n

∑ xij = ai, i=1, 2, …, m (2)

j=1

m

∑ xij = bj, j=1, 2, …, n (3)

i=1

xij ≥ 0, i=1, 2, …, m, j=1, 2, …, n (4)

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

X = (xij) i=1, 2, …, m, j=1, 2, …, n,

удовлетворяющие ограничениям (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

Типы транспортных задач.

1. Задача закрытого типа – сбалансированная или с правильным балансом.

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

m n

∑ ai = ∑ bj

i=1 j=1

2. Задача открытого типа – несбалансированная или с неправильным балансом.

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

m n

∑ ai > ∑ bj - фиктивный поставщик

i=1 j=1

m n

∑ ai < ∑ bj - фиктивный потребитель

i=1 j=1

Математическая модель транспортной задачи может быть записана в векторном виде. Рассмотрим это на примере.

Пример.

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

Поставщики	bj ai	Потребители
20	30	40
40	3	5	7
50	4	6	10

Решение:

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

X =	x11 x12 x13 x21 x22 x23

Запишем матрицу стоимостей

С =	3 5 7 4 6 10

Целевая функция задачи равна сумме произведений всех соответствующих элементов матрицы С и Х.

Z(X) = 3x11 + 5x12 + 7 x13 + 4x21 + 6x22 + 10x23

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

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

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

x11+ x12 + x13 = 40

x21 + x22 + x23 = 50 Это означает, что запасы поставщиков вывозятся полностью.

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

х11 + х21 = 20

х12 + х22 = 30

х13 + х23 = 40 Это означает, что запросы всех потребителей удовлетворены полностью.

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

xij ≥ 0, i=1, 2, j=1, 2, 3

Следовательно, математическая модель рассматриваемой задачи такова:

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

Z(X) = 3x11 + 5x12 + 7 x13 + 4x21 + 6x22 + 10x23

и удовлетворяющие ограничениям

x11+ x12 + x13 = 40

x21 + x22 + x23 = 50

х11 + х21 = 20

х12 + х22 = 30

х13 + х23 = 40

и условиям неотрицательности

xij ≥ 0, i=1, 2, j=1, 2, 3

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

	х11	х12	х13	х21	х22	х23
А =	1	1	1
			1	1	1
1			1
	1				1
		1			1

Каждый столбец имеет n + m строк (2 + 3) и только две из них отличны от 0, равны 1.

Если каждый столбец матрицы, соответствующий переменной хij обозначить вектором Аij, то первая единица в этом столбце стоит на i-ом месте, а вторая на (m + j)-ом месте.

Обозначим через A0 вектор ограничений (правых частей уравнений)

А0 =

а1 а2 в1 в2 в3

=

40 50 20 30 40

Представим систему ограничений в векторном виде

2 3

∑ ∑ Aij = A0

i=1 j=1

В общем виде математическая модель транспортной задачи:

m n

Z(x) = ∑ ∑cijxij min (1)

i=1 j=1

m n

∑ ∑ Aij = A0

i=1 j=1

xij ≥ 0, i=1, 2, …, m, j=1, 2, …, n

Пример 1

Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.

Как следует спланировать перевозку, чтобы её стоимость была минимальной?

Построение математической модели.

Пусть Хij - количество кроватей, отправляемых со склада i в магазин j. Все Хij>=0, и в силу ограничений на возможности поставки со складов и спрос в магазинах должны удовлетворять следующим условиям:

(для предложения)

x11 + x12 + x13 + x14 + x15 = 15

x21 + x22 + x23 + x24 + x25 = 25

x31 + x32 + x33 + x34 + x35 = 20

(для спроса)

x11 + x21 + x31 = 20

x12 + x22 + x32 = 12

x13 + x23 + x33 = 5

x14 + x24 + x34 = 8

x15 + x25 + x35 = 15

Стоимость перевозок равна

F = 1*x11 +0*x12 + 3*x13 + 4+x14 + 2* x15 + 5*x21 + … + 4*x34 + 3*x35

Таким образом, имеет следующую математическую модель

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

Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

План будет называться оптимальным , если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок.

2.12. Решения транспортных задач

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij.

Затем решение задачи разбивается на два этапа:

1. Определение опорного плана.

Нахождение оптимального решения, путем последовательных операций.

2.12.1. Метод северо-западного угла (диагональный)

Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно находить, используя метод "северо-западного угла".

Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, что найденные компоненты плана Хij удовлетворяют горизонтальным и вертикальным уравнениям.