Администрация городского округа Самары

Стр 1 из 6Следующая ⇒

Администрация городского округа Самары

САМАРСКИЙ МУНИЦИПАЛЬНЫЙ ИНСТИТУТ УПРАВЛЕНИЯ

Кафедра математических методов и информационных технологий

Учебно-методический комплекс по дисциплине

«Экономико-математические методы и моделирование»

ЛЕКЦИОННЫЕ МАТЕРИАЛЫ

САМАРА – 2007 г.

Содержание

1. Основные понятия исследования операций.

2. Геометрическая интерпретация задач оптимизации.

3. Задача линейного программирования. Симплекс – метод

4. Двойственные задачи

5. Целочисленное программирование

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

7. Транспортная задача на сети

8. Динамическое программирование

9. Балансовые модели. Модель Леонтьева.

10. Элементы теории матричных игр

11. Литература

Основные понятия исследования операций

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

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

Каждое операционное исследование последовательно проходит следующие основные этапы:

1. Постановка задачи.

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

3. Выбор метода решения задачи.

4. Проверка решения и корректировка модели.

5. Реализация найденного решения на практике.

В зависимости от условий внешней среды, состояния и степени информированности лица, принимающего решение, различают следующие задачи исследования операций.

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

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

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

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

Если информация о вероятностях пребывания объекта в том или ином состоянии отсутствует, то задачу называют задачей принятия решений в условиях неопределенности.

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

Двойственные задачи

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

Запишем общую задачу линейного программирования

→ max

(4.1)

Двойственной задачей к задаче (4.1) называется задача

(4.2)

В таком случае задача (4.1) называется прямой. Исходная и двойственная задачи образуют пару взаимно двойственных задач, при этом любую из них можно рассматривать как прямую задачу.

Переход от прямой задачи к двойственной можно осуществить с помощью следующих правил.

1. Каждому ограничению – неравенству со знаком ≤ соответствует неотрицательная неизвестная y_i двойственной задачи, а каждому ограничению – равенству неизвестная произвольного знака.

2. Каждой неотрицательной неизвестной х_j прямой задачи соответствует ограничение – неравенство со знаком ≥ двойственной задачи, а каждой произвольной по знаку переменной – ограничение в виде равенства.

3. Матрица коэффициентов при неизвестных системы ограничений двойственной задачи получается транспонированием матрицы коэффициентов при неизвестных системы ограничений прямой задачи.

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

5. Коэффициенты при неизвестных y_i целевой функции L двойственной задачи равны свободным коэффициентам системы ограничений прямой задачи.

6. Если целевая функция z прямой задачи максимизируется, то целевая функция L двойственной задачи минимизируется, и наоборот, если целевая функция z прямой задачи минимизируется, то целевая функция L двойственной задачи максимизируется.

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

Справедливы следующие утверждения.

1. Двойственная задача (4.2) имеет решение в том и только в том случае, если имеет решение прямая задача (4.1).

2. Если есть оптимальное решение прямой задачи (4.1), а есть оптимальное решение двойственной задачи (4.2), то выполняется соотношение двойственности

(4.3)

3. Если получено решение одной из пары двойственных задач, например, прямой, то оптимальное решение другой задачи определяется равенством

(4.4)

где С_о – матрица - строка коэффициентов целевой функции Z перед базисными неизвестными оптимального решения прямой задачи, W – матрица коэффициентов при базисных неизвестных оптимального решения в системе ограничений прямой задачи.

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

(4.5)

В качестве примера найдем неотрицательные значения х₁ и х₂, максимизирующие функцию

(4.6)

при наличии ограничений

(4.7)

с помощью перехода к двойственной задаче.

Используя сформулированные выше правила, перейдем к двойственной задаче

(4.8)

(4.9)

Перейдем к канонической задаче. Для этого перенесем свободные коэффициенты в левые части неравенств (4.9) и обозначим получившиеся выражения за новые неизвестные

Кроме того, перейдем к задаче на максимум. Для этого поменяем знаки в правой части целевой функции (4.8). Каноническая задача имеет вид:

; (4.10)

(4.11)

Для решения задачи симплекс – методом необходимо привести систему (4.11) к единичному базису и найти опорное решение. Умножим равенства (4.11) на (-1). Тогда получим

(4.12)

В полученной системе неизвестные y₃ и y₄ выражаются через y₁ и y₂.

Тем самым, система приведена к единичному базису. Приравнивая, свободные неизвестные y₁ и y₂ к нулю, получим базисное решение.

y₁=0; y₂=0; y₃=-5; y₄=-4.

Так как базисные неизвестные отрицательны, полученное решение не является опорным. Для нахождения опорного решения воспользуемся методом исключений Жордана – Гаусса. Выпишем коэффициенты системы (4.12) в таблицу

	y₁	y₂	y₃	y₄
y₃	-4	-3			-5
y₄	-3	-4			-4

Умножим первую строку на (-1) и прибавим ко второй строке. При этом y₃ перестает быть базисной неизвестной.

	y₁	y₂	y₃	y₄
			-1
y₄		-1	-1

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

	y₁	y₂	y₃	y₄
	4/3		-1/3		5/3
y₄		-1	-1

Получим нуль в разрешающем столбце. Для этого ко второй строке прибавим разрешающую. При этом неизвестная y₂, соответствующая разрешающему столбцу, становится базисной и пишется в символьном столбце

	y₁	y₂	y₃	y₄
y₂	4/3		-1/3		5/3
y₄	7/3		-4/3		8/3

Полученной таблице соответствует система равенств

или

(4.13)

Эта система приведена к единичному базису и базисное решение, соответствующее этой системе является опорным

y₁=0; ; y₃=0; (4.14)

Выразим целевую функцию L₁ через свободные неизвестные y₁ и y₃. Для этого подставим равенства (4.13) в (4.10). Тогда задача (4.10); (4.11) с учетом (4.13) примет вид

;

Составим симплекс – таблицу

	y₁	y₂	y₃	y₄
y₂	4/3		-1/3		5/3
y₄	7/3		-4/3		8/3
L₁	-8				-40

В последней строке в первом столбце имеется отрицательная оценка. Следовательно, опорное решение (4.14), соответствующее записанной таблице, не оптимально. Выберем первый столбец за разрешающий. Разделим элементы последнего столбца на соответствующие положительные элементы разрешающего столбца

; .

Наименьший результат соответствует второй строке, поэтому выберем эту строку за разрешающую. Разрешающий элемент равен 7/3. Разделим разрешающую строку на разрешающий элемент.

	y₁	y₂	y₃	y₄
y₂	4/3		-1/3		5/3
y₄			-4/7	3/7	8/7
L₁	-8				-4

Получим нули в разрешающем столбце. Для этого из первой строки вычтем разрешающую, умноженную на 4/3, а к последней прибавим разрешающую, умноженную на 8.

После пересчета имеем

	y₁	y₂	y₃	y₄
y₂			3/7	-4/7	1/7
y₁			-4/7	3/7	8/7
L₁			24/7	24/7	-216/7

В последней строке отрицательных оценок (коэффициентов при неизвестных y_i) нет. Следовательно, опорное решение, соответствующее полученной таблице оптимально.

; ; y₃=0; y₄=0; . (4.15)

Определим решение прямой задачи (4.6); (4.7), используя формулу (4.4)

Здесь - матрица - строка.

Учтем, что базисными неизвестными в оптимальном решении являются y₁ и y₂, и элементами матриц С_о и W являются коэффициенты при базисных неизвестных оптимального решения в равенствах (4.8) и (4.11). То есть

С_о=(24 24);

В этом случае обратная матрица W^-1 имет вид

Отсюда

Таким образом, оптимальное решение (4.6), (4.7) следующее

(4.16)

; ; .

Заметим, что прямая исходная задача (4.6), (4.7) не содержит ограничений в виде равенств, поэтому оптимальное решение (4.16) может быть записано сразу без использования формулы (4.4). Для этого можно воспользоваться равенствами (4.5)

где b₃ и b₄ – элементы последней строки симплекс–таблицы, соответствующей оптимальному решению.

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

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

Простейшая формулировка транспортной задачи, получившая название задачи по критерию стоимости, следующая:

В p пунктах отправления находится соответственно a₁, …, a_p единиц однородного груза (ресурсы), который должен быть доставлен g потребителям в количествах b₁, …, b_g единиц (потребности). Заданы стоимости c_{i k}перевозок из i – го пункта отправления к k– му пункту потребления (коэффициенты затрат). Требуется спланировать перевозки, то есть указать сколько единиц груза должно быть отправлено из любого i-го пункта отправления в любой k- ый пункт потребления так, чтобы максимально удовлетворить потребности, и чтобы суммарные затраты на перевозки были минимальными.

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

Обозначим через x_ik количество единиц продукта, запланированное к перевозке из

i–го пункта в k–ый. Тогда условие задачи можно представить в виде распределительной таблицы.

Таблица 6.1

	b₁	b₂	…	b_k	…	b_g
a₁	c₁₁ x₁₁	c₁₂ x₁₁	…	c_1k x_1k	…	c_1g x_1g
a₂	c₂₁ x₂₁	c₂₂ x₂₂	…	c_2k x_2k	…	c_2g x_2g
…	…	…	…	…	…	…
a_i	c_i1 x_i1	c_i2 x_i2	…	c_ik x_ik	…	c_ig x_ig
…	…	…	…	…	…	…
a_p	c_p1 x_p₁	c_p2 x_p₂	…	c_pk x_p_k	…	c_pg x_pg

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

Суммарные затраты на перевозки равны

Требуется найти n=pg переменных х_ik, удовлетворяющих указанным условиям и минимизирующих функцию z.

Решение такой задачи разбиваем на два этапа:

1. Определение исходного опорного (базисного) решения;

2. Построение последовательных итераций, то есть приближение к оптимальному решению.

Для каждого их этих этапов существует несколько методов.

Рассмотрим первый этап. Для построения опорного решения чаще всего используют один из следующих методов: «северо – западного» угла и метод минимальных затрат.

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

Заполним таблицу 6.1, начиная с левого верхнего (северо – западного) угла, двигаясь затем по строке вправо и по столбцу вниз. Запишем в клетку (1.1) меньшее из числа а₁ и b₁, то есть x₁₁ = min {a₁, b₁}. Если а₁> b₁, то x₁₁=b₁ и первый столбец закрыт, то есть потребности первого потребителя удовлетворены полностью. Двигаясь дальше по первой строке, записываем в соседнюю клетку (1.2) меньшее из чисел a₁ - b₁ и b₂, то есть x₁₂ = min {a₁-b₁, b₂}. Если же а₁ < b₁, аналогично закрывается первая строка (ресурсы первого отправителя исчерпаны), и далее заполняется соседняя клетка (2.1), куда заносится x₂₁ = min {a₂, b₁-а₂}. Этот процесс продолжается до тех пор, пока на каждом этапе не исчерпываются ресурсы а_p и потребности b_g. Может оказаться, что на каком–то промежуточном, а не только последнем этапе, построение опорного плана при внесении очередной величины х_ik закрываются одновременно i–ая строка и k–ый столбец. Это происходит, когда очередной остаток в k–ом столбце будет равен а_i, или остаток в i–ой строке равен b_k. Тогда занесем в следующую по строке или столбцу клетку (в ту из них, которой соответствую меньшие затраты) величину х_ik₊₁ = 0 или (x_i₊₁_k = 0). Такие нули называются, в отличие от пустых клеток, базисными. Они необходимы для предотвращения вырождения опорного плана.

Найдем опорный план методом «северо- западного» угла для транспортной задачи, приведенной в таблице 6.2.

Таблица 6.2.

ai b_k
	⁴	³	⁷	⁸
	⁹	⁵	⁴	²
	⁶	³	⁸	⁴

Заполним таблицу, начиная с клетки (1.1). х₁₁ = min {60; 40}= 40. Первый столбец закрывается (потребности удовлетворены полностью) и во всех его остальных клетках ставится прочерк. Запасы первого поставщика не израсходованы на 60-40=20 единиц. Сравниваем с потребностями второго потребителя b₂ = 100. Тогда х₁₂= min {20; 100}= 20. Так как запасы первого поставщика исчерпаны, то в двух последних клетках первой строки ставим прочерки. Далее рассмотрим клетку (2, 2).

х₂₂= min {140; 80}, где 140 – запасы второго поставщика, а 80 – оставшиеся потребности второго потребителя. Таким образом, х₂₂= 80, а в оставшейся клетки второго столбца ставим прочерк. Рассмотрим клетку (2, 3). х₂₃= min {60; 60}= 60. При этом одновременно закрываются вторая строчка и третий столбец, что означает полное удовлетворение потребностей третьего потребителя и исчерпание ресурсов второго поставщика. Поэтому, чтобы избежать вырождения, в соседней к (2, 3) пустой клетке с наименьшей стоимостью перевозок (2, 4) ставим ноль, а клетке (3, 3) ставим прочерк. Заполняем оставшуюся клетку (3, 4). х₃₄= min {80; 80}= 80. Тем самым получено опорное решение. Таблица 6.3

a_i b_k
	⁴	³ 20	⁷	⁸
	⁹	⁵	⁴	²
	⁶	³	⁸	⁴

Найдем общую стоимость перевозки как сумму произведений объемов перевозок х_ik на соответствующие стоимости

z= 40·4 + 20·3 + 80·5 + 60·4 + 80·4 = 1180

2. Метод минимальных затрат.

В правиле «северо- западного» угла не учитываются величины затрат с_ik, а, значит, опорное решение может быть далеким от оптимального. Поэтому в дальнейших расчетах может потребоваться много шагов (итераций) для достижения оптимального решения. Число итераций, как правило, можно сократить, если исходное решение строить по усовершенствованному методу минимальных затрат. Сущность его состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной с_ik. Начинаем заполнение таблицы с клетки, которой соответствует наименьший элемент с_ik из всей таблицы (в таблице 6.2 начинаем с клетки (2, 4), где с_ik =2). Затем остаток по столбцу или строке помещаем в клетку того же столбца или строки, которой соответствует следующее по величине значение с_ik и так далее. Таким образом, последовательность заполняемых клеток определяется по величинам с_ik, а помещаемые в этих клетках величины х_ik определяются как и в правиле «северо- западного» угла. В результате для таблице 6.2 получаем другое опорное решение.

Таблица 6.4

a_i b_k
	⁴ 40₍₆₎	³ 20₍₅₎	⁷	⁸
	⁹	⁵ 0₍₃₎	⁴ 60₍₂₎	² 80₍₁₎
	⁶	³ 80₍₄₎	⁸	⁴

Индексы в скобках в таблице 6.4. показывают порядок заполнения. Начинаем с клетки (2, 4) с наименьшей среди стоимостей с_ik (с₂₄ = 2), поэтому

х₂₄= min {140; 80}= 80. Так как потребности четвертого потребителя удовлетворены, прочеркиваем остальные клетки четвертого столбца. У второго поставщика осталось 60 единиц товара. Находим минимальное значение с_ik для оставшихся клеток второй строки. Это с₂₃= 4. Поэтому х₂₃= min {60; 60}= 60. При этом одновременно исчерпываются ресурсы второго поставщика и удовлетворяют потребности третьего потребителя. Чтобы избежать вырождения, ставим базисный ноль в клетке (2, 2) с наименьшим тарифом с₂₂ =5. В остальных клетках второй строки и третьего столбца ставим прочерки. Затем рассматриваем второй столбец. Здесь у оставшихся клеток (1, 2) и (3, 2) тарифы равны. Заполним клетку (3, 2) с максимальным х_i из этих двух; х₃₂= 80. Оставшиеся 20 единиц помещаем в клетку (1, 2), то есть х₁₂= 20. Ресурсы третьего поставщика исчерпаны, поэтому в пустой клетке третьей строки ставим прочерк. Наконец заполняем оставшуюся клетку (1, 1), х₁₁= 40.

Общая стоимость по такому плану равна:

z = 40·4 + 20·3 + 80·3 + 60·4 + 80·2 = 860

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

Введем понятие цикла. Циклом называется набор клеток, в котором две и только две соседние расположены в одном столбце или одной строке, причем последняя клетка находится в одном столбце или одной строке с первой.

Рассмотрим пример:

Для таблицы 6.3 построим цикл, начинающийся в клетке (3.1).

Решение имеет вид:

Таблица 6.5

a_i b_k
	⁴ [-]40	³ [+]20	⁷	⁸
	⁹	⁵ [-]80	⁴	² [+]0
	⁶ [+]	³	⁸	⁴ [-]80

Здесь все пустые клетки обозначены точками. Начинаем с клетки (3.1), в которой ставим «+», как и в дальнейшем в нечетных клетках цикла. Во второй клетке цикла (1.1) ставим « - », как и во всех четных клетках цикла. За исключением первой в цикл входят только занятые клетки, причем только две из строки и столбца, так что при его обходе можно вернуться в исходную клетку. Можно доказать, что такой цикл единственный, причем только из занятых клеток нельзя образовать цикла.

Распределительный метод описывается следующим алгоритмом:

1. Располагаем исходные данные в распределительной таблице.

2. Строим опорное решение. При этом должны оказаться занятыми r = p+g-1 клеток.

3. Производим оценку первой свободной клетки путем построения для нее цикла и вычисления по этому циклу величины

где в первую сумму входят тарифы клеток цикла со знаком «+», а во вторую со знаком « - ».

Если Δ _st < 0, то переходим к пункту 4.

Если Δ _st ≥ 0, то оцениваем следующую свободную клетку до тех пор, пока обнаружим клетку с отрицательной оценкой Δ _st. Если все Δ _st неотрицательны, то решение соответствующее таблице является оптимальным.

4. Находим λ = min {х_ij}, где х_ij – значения величины перевозок в клетках со знаком

«-» затем прибавляем λ ко всем клеткам цикла со знаком «+» и отнимаем из всех клеток со знаком «-». После этого возвращаемся к пункту 3.

Оценки свободных клеток связаны с определенной таблицей. На каждом новом этапе после 4 пункта оценки одних и тех же клеток будут изменяться, поэтому на каждом этапе необходимо пересчитывать оценки свободных клеток Δ _st.

При выполнении пункта 3 целесообразно выбирать для оценки сначала клетки с минимальными тарифами с_ik.

Рассмотрим приведенный алгоритм для таблицы 6.3.

Таблица 6.6

a_i b_k
	⁴	³	⁷	⁸
	⁹	⁵ [-]80	⁴	² [+]0
	⁶	³ [+]	⁸	⁴ [-]80

В таблице 6.6 построен цикл для свободной клетки (3.2), имеющий наименьший тариф с₃₂=3.

с₃₂==(3+2)-(5+4)=-4< 0

λ =min{80; 80}=80

Выполнив пункт 4, имеем таблицу 6.7. Оценим сначала клетку (3.4).

Δ ₃₄=9-5=4> 0

Таблица 6.7

a_i b_k
	⁴	³	⁷	⁸
	⁹	⁵ [+]0	⁴	² [-]80
	⁶	³ [-]80	⁸	⁴ [+]

Затем остальные свободные клетки (3, 3), (3, 1), (2, 1), (1, 3), (1, 4).

Δ ₃₄=6> 0; Δ ₃₁=2> 0; Δ ₁₃=5> 0; Δ ₁₄=8> 0; Δ ₂₁=3> 0.

Таким образом, решение в таблице 6.7 является оптимальным. Заметим, что в данном примере метод минимальных затрат сразу дал оптимальное решение (см.таблицу 6.4), а для правила «северо – западного» угла потребовалась одна итерация.

Распределительный метод обладает существенным недостатком, заключающимся в том, что для выполнения одной итерации требуется строить большое количество оценочных циклов. Этот недостаток устранен в методе потенциалов. Рассмотрим метод потенциалов на примере таблицы 6.3

Каждому поставщику a_i сопоставил величину U_i, называемую потенциалом. Каждому потребителю b_j сопоставим потенциал V_j.

Составим уравнение вида V_j-U_i-c_ij=0 для всех занятых клеток. Для удобства перепишем эту таблицу в виде:

Таблица 6.8

a_i b_k	V₁	V₂	V₃	V₄
U₁	⁴	³	⁷	⁸
U₂	⁹	⁵	⁴	²
U₃	⁶	³	⁸	⁴

Получаем: V₁-U₁=4; V₂-U₁=3; V₂-U₂=5; V₃-U₂=4; V₄-U₂=2; V₄-U₃=4.

Полагая одну из неизвестных (наиболее часто встречающуюся) равной нулю (здесь U₂=0), найдем все остальные.

V₁=6; V₂=5; V₃=4; V₄=2; U₁=2; U₃₌-2.

Проверим выполнение условий оптимальности для занятых клеток. Для этого должно выполняться соотношение δ _ij = V_j - U_i-C_ij 0.

δ ₁₃=V₃-U₁-C₁₃=4-2-7=-5< 0

δ ₁₄=V₄ - U₁-C₁₄=2 - 2 - 8 = - 8 < 0

δ ₂₁=V₁ - U₂ - C₂₁=6 – 0 - 9= - 3 < 0

δ ₃₁=V₁ - U₂ - C₃₁ = 6 + 2 - 6 = 2 > 0

δ ₃₂=V₂ - U₃ - C₃₂ = 5 + 2 – 3 = 4 > 0

δ ₃₃=V₃ - U₃ - C₃₃ = 4 + 2 - 8 = -2 < 0

Построим цикл для клетки с наибольшем нарушением δ _ij. Это клетка (3, 2). Как в распределительном методе пересчитаем x_ij для клеток цикла. Полученный результат запишем в таблице 6.9.

Таблица 6.9

a_i b_k	V₁	V₂	V₃	V₄
U₁	⁴	³	⁷	⁸
U₂	⁹	⁵	⁴	²
U₃	⁶	³	⁸	⁴

Опять проверяем на оптимальность. Имеем систему из 6 уравнений с 7 неизвестными.

V₁ - U₁ = 4; V₂ - U₁ = 3; V₂ - U₂ = 5; V₂ - U₃ = 3; V₃ - U₂ = 4; V₄ - U₂ = 2.

Система имеет множество решений. Полагая V₂=5, находим U₁=2; U₂=0; U₃=2;

V₃ = 4; V₄ = 2; V₁ = 6.

В таком случае δ ₁₃ = - 5; δ ₁₄ = - 8; δ ₂₁ = - 3; δ ₃₁ = -2; δ ₃₃ = - 6; δ ₃₄ = - 4.

Все δ _ij, соответствующие пустым клеткам, отрицательны. Значит, решение в таблице 6.9 является оптимальным (оно совпадает с таблицей 6.4 и таблицей 6.7).

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

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

p_i- объемом поставок (p_i > 0) или объемом потребления (p_i < 0). Для перевалочных пунктов p_i=0. В середине каждого звена проставляется стоимость перевозки c_ij. Направление грузопотока характеризуют стрелками. Цифра около стрелки показывает величину перевозки x_ij. Если пропускная способность звена ограничена величиной d_ij, то эта величина проставляется знаменателем стоимости с_ij. Наличие звена означает возможность только одностороннего движения. В случае, когда допустимы перевозки в обоих направлениях между p_i и p_j, эти два пункта должны быть соединены парой коммуникаций противоположного направления.

12 3 4 5 6 Следующая ⇒