Курсовая работа по «Теории принятия решения»

Транспортную таблицу  начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: х₁₁= 
= min(a₁,b₁) Если а₁ < b₂, то х₁₁ = a₁ и предложение первого поставщика полностью исчерпано. Первая строка вычеркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: х₂₁= min(a₂,b₁-a₁). Если b₁-a₁ <a₂ то х₂₁ = b₁-a₁. Спрос первого потребителя удовлетворен. Первый столбец вычеркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечении второй строки и второго столбца, переходят к заполнению следующей третьей клетки второй строки, либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос. Последняя заполненная клетка находится в последнем n-м столбце и последней m-й строке.

 

2.1.4. Оптимальный план транспортной задачи.

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

Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно  m+n-1, где m – число производителей, n – число потребителей, то план перевозок невырожденный.

Если число заполненных клеток транспортной таблицы меньше m+n-1, то план перевозок вырожденный.

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

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

 

2.1.5. Получение оптимального плана транспортной задачи с использованием метода потенциалов.

Шаг 1. Получение начального плана перевозок по методу "северо-западного" угла, минимального элемента, Фогеля или любым другим методом.

Шаг 3. Проверка плана на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m+n-1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.

Шаг 3. Проверка плана на оптимальность.

Шаг 3.1. Определение потенциалов производителей и потребителей. Составляют систему уравнений для заполненных клеток транспортной таблицы: U_i + V_j = С_ij , где i,j – номера строк и столбцов на пересечении которых стоят заполненные клетки, U_i – потенциал i-го поставщика,  
V_j – потенциал j-го потребителя, С_ij – тариф на перевозку из пункта i  
в пункт j. Число уравнений в системе равно т+п-1, а число неизвестных U_i – и V_j равно т+п. Для решения данной системы одно из неизвестных выбирают произвольно. Обычно полагают U_i = 0. Решая систему уравнений, находят значения потенциалов U_i и V_j, i=1,m ; j=1,n .

Шаг 3.2. Определение суммы потенциалов (косвенных тарифов) для свободных клеток: C1_qp = U_q + V_p , где q и р – номера строк U столбцов, на пересечении которых стоит свободная клетка, U_q – потенциал q-гo поставщика, V_p – потенциал р-го потребителя, C1_qp – косвенные тарифы.  

Шаг 3.3. Проверка на оптимальность. Для каждой свободной клетки транспортной таблицы составляется разность между C1_qp и C_qp(косвенным и реальным тарифами) ∆_qp= C1_qp – C_qp. Если все ∆_qp≥0, то полученный план оптимален. Если хотя бы для одной свободной клетки ∆ _qp<0, то план может быть улучшен. Переход к шагу 4.

Шаг 4. Улучшение плана.

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

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

Шаг 4.2. Выбор переменной, выводимой из списка базисных переменных. Заполнение клетки, выбранной на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и заканчивающийся в выбранной свободной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. При этом в каждой клетке таблицы, являющейся вершиной цикла, соединяют обязательно горизонтальный и вертикальный отрезки. В свободной клетке условно ставят знак "+", а в остальных вершинах цикла, чередуясь, ставят "-" и "+". Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком "-" , которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком "+" , и отнимают от значений, стоящих в клетках со знаком "-" . При таком перераспределении общий баланс не изменяется. Свободная клетка заполняется, а клетка со знаком "-" , которой соответствует наименьшее количество продукции, становится свободной; соответствующую ей переменную исключают из списка базисных.

Для нового плана повторяют все  действия, т. е. переходят к шагу 3.

 

2.2. Блок-схема решения задачи.

 
2.3. Физическая интерпретация задачи.

 

У трех поставщиков А₁, А₂, А₃ находится соответственно 100, 150, 50 кг отрубей, которые должны быть доставлена потребителям В₁, В₂, В₃, В₄ в количестве 75, 80, 60, 85 кг. Стоимость доставки кг отрубей от поставщика А₁ к указанным потребителям равна 6, 7, 3, 5 руб. Стоимость доставки кг отрубей от поставщика А₂ к указанным потребителям равна 1, 2, 5, 6 руб. Стоимость доставки кг отрубей от поставщика А₃ к указанным потребителям равна 8, 10, 20, 1 руб. Необходимо найти оптимальное решение доставки отрубей от поставщиков к потребителям, минимизирующее стоимость доставки.

 

2.4. Аналитическое решение задачи.

 

						ai
	6	7	3	5		100
С=	1	2	5	6		150
	8	10	20	1		50
bi	75	80	60	85

 

Табл.7

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	6	7	3	5	100
А2	1	2	5	6	150
А3	8	10	20	1	50
Потребность	75	80	60	85

Рассмотрим маршрут от поставщика А₁ к потребителю В₁(ячейка А₁В₁). Запасы поставщика А₁ составляют 100 кг. Потребность потребителя В₁ составляет 75 кг. От поставщика А₁ к потребителю В₁ будем доставлять min{100,75}=75 кг.  Разместим в ячейку А₁В₁ значение равное 75. Мы полностью удовлетворили потребность потребителя В₁. Вычеркиваем столбец 1 таблицы, т.е исключаем из дальнейшего его рассмотрения.

 Табл.8

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	7	3	5	100
А2	1	2	5	6	150
А3	8	10	20	1	50
Потребность	75	80	60	85

Рассмотрим маршрут доставки поставщика А₁ к потребителю В₂ (ячейка А₁В₂). Запасы поставщика А₁ составляют 25 кг. Потребность потребителя В₂ составляет 80 кг. От поставщика А₁ к потребителю В₂ будем доставлять min{25,80}=25 кг. Разместим в ячейку А₁В₂ значение равное 25. Мы полностью израсходовали запасы поставщика А₁. Вычеркиваем строку 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.

Табл.9

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	25   7	3	5	100
А2	1	2	5	6	150
А3	8	10	20	1	50
Потребность	75	80	60	85

Рассмотрим маршрут от поставщика А₂ к потребителю В₂ (ячейка А₂В₂). Запасы поставщика А₂ составляют 150 кг. Потребность потребителя В₂ составляет 55 кг. От поставщика А₂ к потребителю В₂ будем доставлять min{150,55}=55 кг. Разместим в ячейку А₂В₂ значение равное 55. Мы полностью удовлетворили потребность потребителя В₂. Вычеркиваем столбец 2 таблицы, т.е. исключаем его из дальнейшего рассмотрения.

Табл.10

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	25   7	3	5	100
А2	1	55   2	5	6	150
А3	8	10	20	1	50
Потребность	75	80	60	85

Рассмотрим маршрут доставки от поставщика А₂ к потребителю В₃ (ячейка А₂В₃). Запасы поставщика А₂ составляют 95 кг. Потребность потребителя В3 составляет 60 кг. От поставщика А₂ к потребителю В₃ будем доставлять min{60,95}=60 единиц продукции. Разместим в ячейку А₂В₃ значение равное 60. Мы полностью удовлетворили потребности потребителя В₃. Вычеркиваем столбец 3 из таблицы, т.е. исключаем его из дальнейшего рассмотрения.

Табл.11

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	25   7	3	5	100
А2	1	55   2	60   5	6	150
А3	8	10	20	1	50
Потребность	75	80	60	85