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

ЛУКИНОВА С. Г.

ШАТОХИНА Л. В.

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Учебное пособие

Красноярск 2013

УДК 519.8(075.8)

ББК 65в631я73

Лукинова С. Г., Шатохина Л.В.Методы оптимальных решений .Учебное пособие. – Красноярск: Красноярский филиал ФГБОУ ВПО «Московский государственный университет экономики, статистики и информатики (МЭСИ)», 2013.- 76 с.

Рецензент: А.К. Шлёпкин, зав. кафедрой прикладной математики

Красноярского государственного аграрного университета,

профессор, д-р физ.-мат. наук.

© С.Г. Лукинова, Л.В. Шатохина 2013

© ФГБОУ ВПО «Московский государственный университет экономики, статистики и информатики (МЭСИ)» Красноярский филиал, 2013

Содержание

1. Транспортная задача.. 6

1.1 Экономическая постановка и математическая модель транспортной задачи.. 6

1.2 Методы нахождения начального плана перевозок. 8

1.3 Метод потенциалов решения транспортной задачи.. 10

1.4 Открытая модель транспортной задачи.. 20

2. Матричные игры, их применение к решению оптимизационных задач.. 23

2.1 Основные понятия теории матричных игр. 23

2.2 Решение матричных игр в чистых стратегиях. 26

2.3 Решение матричной игры в смешанных стратегиях. 30

2.4 Сведение матричной игры к задаче линейного программирования. 34

2.5 Статистические игры.. 38

3. Графы, их применение в решение оптимизационных задач.. 45

3.1 Определение графа.. 45

3.2 Матрицы смежности и инцидентности.. 47

3.3 Путь и цикл в графе. 47

3.4 Связность графа, деревья. 49

3.5 Виды графов. 50

3.6 Сети. Критический путь. 55

Вопросы к экзамену.. 60

ИТОГОВЫЙ ТЕСТ.. 62

КОНТРОЛЬНАЯ РАБОТА.. 64

Библиографический список.. 75

Транспортная задача

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

Экономическая постановка:

Пусть имеется mпунктов поставщиков с объемами продукции

, где i=1,2,…m

а также nпунктов потребления с объема­ми потребления

,где j=1,2,…n

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

Математическая модель:

пусть - объем планируемой перевозки продукции от i-го по­ставщика к потребителю .

Тогда суммарная стоимость перевозок равна

или

Условия ограничений

по запасам:

по потребностям:

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

,

,

Если в транспортной задаче выполняется условие

то она называется задачей закрытого типа. Транспортная задача закрытого типа всегда имеет решение.

Если в транспортной задаче суммарные запасы не совпадают с суммарными потребностями

то она называется задачей открытого типа.

Транспортная задача открытого типа решается приведением к задаче закрытого типа, для чего вводится фиктивный поставщик или фиктивный потребитель. Если суммарные потребности пре­вышают суммарные запасы, то вводится фиктивный поставщик с объемом производства (запасов)

Если суммарные запасы превышают суммарные потребно­сти, то вводится фиктивный потребитель с потребностью

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

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

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

Потребители Поставщики			-
			-
…
			-

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

Методы нахождения начального плана перевозок

Решение транспортной задачи, как и любой задачи линейного программирования, начинается с нахождения начального опорного плана. Наиболее часто применяют два метода построений начального плана перевозок.

Метод «северо-западного угла»

Этот метод заключается в следующем: величина максимально возможного количества товара помещается в «северо-западный угол» таблицы, затем заполняется соседняя клетка в строке или столбце

Недостаток метода «северо-западного угла» заключается в том, что при построении опорного плана совсем не учитывается стоимость перевозок с_ij.