VIII Международная студенческая научная конференция Студенческий научный форум - 2016

В термин «транспортной задачи» входит широкий круг поставленных задач с различными математическими моделями. Классический вид данных задач – это выбор наиболее выгодного с экономической точки зрения плана перевозок различных продуктов из пунктов их производства в пункты потребления. Решать задачи такого рода проще всего, применяя линейное программирование. Оно является одной из областей математики, где разработаны теории и численные методы решения многомерных задач, включающих в себя различные ограничения.

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

Транспортная задача может быть представлена в сетевой, т.е. схематичной, или же в матричной (табличной) форме. Также она может решаться с ограничениями и без них.

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

1. Метод дифференциальных рент

Метод дифференциальных рент представляет собой способ решения транспортной задачи с помощью линейного программирования. В основу метода положена идея рассмотрения процесса решения задачи как процесса стабилизации эконом, системы. Метод как бы имитирует формирование дифференциальной ренты в модели транспортных перевозок и увязки спроса и предложения. В отличие, например, от решения транспортной задачи методом потенциалов, где с самого начала производится распределение всей продукции, которое затем последовательно улучшается, в случае применения метода дифференциальных рент вначале распределяется часть продукции, но зато оптимально: «потребители» прикрепляются к «поставщикам» наиболее экономичным, в смысле стоимости перевозок.

Потреби́тель — это гражданин, который имеет намерение приобрести какой-либо товар целью личного использования, не связанного с предпринимательской деятельностью.

Д.Ф. Кеннеди (35-й президент Соединенных Штатов Америки) в свое время сказал, что все мы, т.е. население планеты, являемся потребителями. Данная мысль позднее легла в основу для утверждения Всемирного дня защиты прав потребителей.

С уверенностью можно сказать, что в круговороте «деньги-товар-деньги» потребитель является основным объектом, на которого нацелено производство, оказание услуг различного характера, за исключением лишь военно-промышленного комплекса. Так как потребитель – это главное звено в экономике, то не трудно догадаться, что производитель, лишившийся его, обречен на банкротство. Поэтому, можно считать, что защита прав потребителей, а также их интересов, является приоритетным направлением в государственной деятельности. То есть рядовой-покупатель должен быть уверен, что при проведении какого-либо действия по купле-продаже или заказе услуги, он будет защищен государством.

Классификация потребителей:

1. Конечные пользователи — потребители, непосредственно использующие продукт или услугу.

2. Агенты влияния — потребители, целью которых является получение выгоды от продукта или услуги.

3. Рекомендатели — покупатели, мнение которых является решающим в принятии решения.

4. Держатели бюджета — осуществляют контроль в приобретении продукта или услуги.

5. Лица, принимающие решения — держатели бюджета либо лица более высокой иерархии, чем они.

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

Модели принятия решений о покупке

Этапы принятия решения согласно типичной модели:

• Осознание потребности;

• Поиск информации;

• Анализ альтернатив;

• Покупка;

• Поведение после покупки.

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

Ответственность поставщика

Покупатель вправе предъявить поставщику требования по замене или возврате денежных и иных средств, с помощью которых был совершен процесс куплю-продажи, если качество товара не соответствует изначально изложенным.

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

Дальнейшие этапы прикрепления потребителей к поставщикам связаны с условным повышением стоимости перевозок за счет присвоения поставщикам дополнительной стоимости — ренты — и повышения «кредитоспособности» не вошедших в план потребителей. В момент полного распределения продукции и окончательного расчета полученный план прикрепления потребителей к поставщикам оптимален.

Алгоритм решения задачи методом дифференциальных рент

При решении ТЗ с помощью метода дифференциальных рент наилучшим образом распределяется часть продукции между потребителями и на последующих итерациях и постоянно уменьшается общая величина нераспределенных поставок.

Алгоритм метода:

1) В каждом столбце определяется минимальный тариф и соответствующая клетка помечается.

2) Отмеченные клетки заполняются максимально возможными поставками.

3) Оцениваются поставщики:

а) строки, соответствующие поставщикам, запасы которых неисчерпаны, являются положительными;

б) строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности отмеченных потребителей неудовлетворены (с учетом всего столбца), являются отрицательными;

в) строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности отмеченных потребителей удовлетворены (с учетом всех заполненных клеток столбца), имеют нулевую оценку; при этом, если заполненная клетка в нулевой строке связана через столбец с заполненной клеткой в отрицательной строке, то данная нулевая строка считается отрицательной, во всех других случаях – положительной.

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

5) Среди полученных разностей, отличных от 0, определяется минимальная. Это число называется промежуточной рентой.

6) Строится новая таблица, при этом тарифы, которые стоят в положительных строках, подвергаются переписыванию без изменения, а тарифы - в отрицательных строках, увеличиваются на величину промежуточной ренты.

7) Переход к пункту 1.

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

Сущность алгоритма метода дифференциальных рент

Далее будет рассмотрен метод потенциалов. Особенность этого метода заключается в том, что сначала определяется некоторый опорный план, какое-то неотрицательное решение задачи, а затем шаг за шагом план улучшается до тех пор, пока не становится оптимальным. Метод разрешающих слагаемых, дифференциальных рент, венгерский и некоторые другие основаны на противоположном принципе; в них план с самого начала соответствует критерию оптимальности, но должен проверяться на допустимость. Если план оказывается недопустимым, т.е. если сумма поставок оказывается меньше (а иногда и больше) мощностей поставщиков (или спросов потребителей), а так именно и бывает на первой и промежуточных итерациях, то постепенно, шаг за шагом план доводится до допустимого. Как только это достигается, решение считается законченным, и полученный план оказывается оптимальным. Следовательно, до самого конца решения план не является допустимым, удовлетворяя при этом критерий оптимальности, и является условно оптимальным. В результате все методы, которые относятся к этой группе, называются методами условно оптимальных планов.

Основная идея метода дифференциальных рент состоит в том, что первоначально в каждом столбце отмечаются кружками или полужирным курсивом минимальные показатели сij и в клетки с выделенными минимальными стоимостями записываются величины поставок хij. Если вся продукция окажется распределенной и спрос потребителей удовлетворен полностью, это означает, что получен оптимальный план. Если это условие не выполняется, начинается итеративный процесс, в ходе которого матрица C = cij изменяется особым образом и процесс распределения поставок повторяется, но уже в соответствии с новой матрицей стоимости поставок. При этом общее количество распределенной продукции

m n

∑ ∑ x

i =1i j =1j

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

Пример решения транспортной задачи методом дифференциальных рент.

Первая итерация.

В каждом столбце отметим минимальный показатель затрат сij.

Распределение продукции по клеткам с выделенными минимальными значениями тарифов начинается с первого столбца, при этом в клетку записывается поставка x_ij min_a_i, b_j.

ai bj	13	5	13		12					13				Оценка поставщи- ков
14	16	26	13	12	24				3				+1
14	5	2 5	19		27					9	2		–4
14	29	23	25		16					8				+14
14	2 13	25	14		1			15	21				–11
Разность тарифов	14	21	–			1			1

Нераспределённый остаток равен 1+14 = 15.

Эта схема распределения не является допустимым планом поставок, т.е. не является решением задачи. В связи с этим далее необходимо произвести оценку каждого поставщика и использовать их свободные ресурсы.

Разность тарифов – это разность наименьшего тарифа в положительных строках и отмеченного тарифа в этом столбце. Если в столбце есть отмеченный тариф в положительной строке, то ставим –. Наименьшая из вычисленных разностей – это промежуточная рента.

Вторая итерация.

По отрицательным строкам тарифы увеличиваем на величину промежуточной ренты. Тарифы по положительным строкам переписываем в новую таблицу без изменения.

ai bj	13			5		13				12					13				Оценка поставщи- ков
14	16			26		13		12	24					1		3	-3
14	6			5	3	20			28					9		3	-0
14	29			23		25				12		16		8				+2
14	13	3	26			15			0		16		22				+1
Разность тарифов	–			20			3		–					5

Нераспределённый остаток равен 2+1 = 3.

Третья итерация.

ai bj	13			5		13				12					13						Оценка поставщи- ков
14	19			29		12		15		27						2	6		–2
14	9			5	6	23				31				9				6	–0
14	29			23		25				12		16		8						+2
14	13	3	26			1	15		0		16		22						–0
Разность тарифов	26			17		10				–						2

Нераспределённый остаток равен 2.

Четвёртая итерация.

ai bj	13			5		13				12			13					Оценка поставщи- ков
14	21			31		12		17		29		2		8
14	11			5	8	25				33			9		8
14	29			23		25				12	16	2		8
14	13	5	28			1	17		18			24
Разность тарифов

Нераспределённый остаток равен 0, следовательно, получен допустимый оптимальный план.

1. Метод потенциалов

Метод потенциалов - является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить, отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

Общий принцип определения оптимального пла­на транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала на­ходят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.

Составим двойственную задачу

1. , - любые

2.

3.

Пусть есть план

Теорема (критерий оптимальности):Для того чтобы допустимый план перевозок в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа , , что

если ,

если.

числа и называются потенциалами пунктов отправления и назначения соответственно.

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план. Для этого плана, в ко­тором базисных клеток, можно определить потенциалы и так,чтобы выполнялось условие (6). Поскольку система (2)-(4) содержит уравнений и неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (6) определяются остальные потенциалы и для каждой из свободных клеток вы­числяются величины . Если оказалось, что , то план оп­тимален. Если же хотя бы в одной свободной клетке , то план не яв­ляется оптимальным и может быть улучшен путем переноса по циклу, соот­ветствующему данной свободной клетке.

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

Процесс улучшения плана продолжается до тех пор, пока не будут выполнены условия если .

Пример решения транспортной задачи

Задача. На четыре базы A₁, A₂, A₃, A₄ поступил однородный груз в следующем количестве: а₁ тонн - на базу А₁, а₂ тонн - на базу А₂, а₃ тонн - на базу А₃, а₄ тонн - на базу А₄. Полученный груз требуется перевезти в пять пунктов: b₁ тонн - на базу B₁, b₂ тонн - на базу B₂, b₃ тонн - на базу B₃, b₄ тонн - на базу B₄, b₅ тонн - на базу B₅. Расстояния между пунктами назначений указаны в матрице расстояний.

пункты отправления	пункты назначения						запасы
	B1	B2	B3	B4	B5
A1	30	24	11	12	25	21
A2	26	4	29	20	24	19
A3	27	14	14	10	18	15
A4	6	14	28	8	2	25
потребности	15	15	15	15	20

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

Решение. Проверим сбалансированность транспортной задачи, для этого необходимо чтобы

, .

1. Решим задачу диагональным методом или методом северо-западного угла.

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

пункты отправления	B1	B2	B3	B4	B5	запасы
A1	15	6	―	―	―	21	6	0	0	0	0	0	0
A2	―	9	10	―	―	19	19	19	10	0	0	0	0
A3	―	―	5	10	―	15	15	15	15	15	10	10	10
A4	―	―	―	5	20	25	25	25	25	25	25	25	20
потребности	15	15	15	15	20
	0	15	15	15	20
	0	9	15	15	20
	0	0	15	15	20
	0	0	5	15	20
	0	0	0	15	20
	0	0	0	5	20
	0	0	0	0	20

Получен следующий план:

	15	6	0	0	0
X0=	0	9	10	0	0
	0	0	5	10	0
	0	0	0	5	20

Полученный план невырожденный. F(X₀)=15·30+6·24+9·4+10·29+5·14+10·10+5·8+20·2=1170.

2. Метод наименьшей стоимости.

пункты отправления	B1		B2		B3		B4		B5		запасы
A1	6	30	×	24	15	11	×	12	×	25	21	21	21	21	21	6	6
A2	4	26	15	4	×	29	×	20	×	24	19	19	4	4	4	4	0
A3	×	27	×	14	×	14	15	10	×	18	15	15	15	15	0	0	0
A4	5	6	×	14	×	28	×	8	20	2	25	5	5	0	0	0	0
потребности	15		15		15		15		20
	15		15		15		15		0
	15		0		15		15		0
	10		0		15		15		0
	10		0		15		0		0
	10		0		0		0		0
	6		0		0		0		0

Получили вырожденный опорный план

	6	0	15	0	0
X0=	4	15	0	0	0
	0	0	0	15	0
	5	0	0	0	20

F(X₀)=6·30+15·11+4·26+15·4+15·10+5·6+20·2=729.

3. Метод двойного предпочтения.

пункты отправления	B1		B2		B3		B4		B5		запасы
A1	6	30	×	24	15	11	×	12	×	25	21	21	21	21	21	6	6
A2	4	26	15	4	×	29	×	20	×	24	19	19	4	4	4	4	0
A3	×	27	×	14	×	14	15	10	×	18	15	15	15	15	0	0	0
A4	5	6	×	14	×	28	×	8	20	2	25	5	5	0	0	0	0
потребности	15		15		15		15		20
	15		15		15		15		0
	15		0		15		15		0
	10		0		15		15		0
	10		0		15		0		0
	10		0		0		0		0
	6		0		0		0		0

Получили вырожденный опорный план

	6	0	15	0	0
X0=	4	15	0	0	0
	0	0	0	15	0
	5	0	0	0	20

F(X₀)=6·30+15·11+4·26+15·4+15·10+5·6+20·2=729.

4. Метод аппроксимации Фогеля.

пункты отправления	B1		B2		B3		B4		B5		запасы	столбец-разность
A1	×	30	×	24	15	11	6	12	×	25	21	1	1	1	1	1	1	1
A2	×	26	15	4	×	29	4	20	×	24	19	16	16	4	4	9	к	к
A3	×	27	×	14	×	14	5	10	10	18	15	4	4	4	4	4	4	к
A4	15	6	×	14	×	28	×	8	10	2	25	4	6	6	к	к	к	к
потребности	15		15		15		15		20
строка-разность	20		10		3		2		16
	к		10		3		2		16
	к		к		3		2		16
	к		к		3		2		6
	к		к		3		2		к
	к		к		3		2		к
	к		к		к		к		к

Получили невырожденный опорный план

	0	0	15	6	0
X0=	0	15	0	4	0
	0	0	0	5	10
	15	0	0	0	10

F(X₀)=15·6+15·4+15·11+5·10+4·20+6·12+10·18+10·2=717.

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

Так как взятый нами план является вырожденным, то вводим ε - некоторое число близкое к 0.

Составим систему уравнений:

u1

+

v1

=

30

Пусть

u1

=

0

v1

=

30

u1

+

v2

=

8

c14

=

12

u2

+

v1

=

26

u3

=

-14

v3

=

11

u1

+

v5

=

26

>

c15

=

25

u2

+

v2

=

4

u4

=

-24

v4

=

24

u2

+

v3

=

7

Код для цитирования: Скопировать