|
|
| Контрольная: Транспортная задача |
Ищем в таблице 5 минимальную стоимость – это ячейка (3,4), т.е. 3-я строка и
4-й столбец. Определяем минимум из запасов в 3-й строке и потребностей в 4-м
столбце. Он равен 125. Записываем в скобках в ячейку (3,4) 125 и вычеркиваем
4-й столбец, а запасы 3-й строки уменьшаем на 125 единиц, т.е. 160 - 125 = 35
ед.
Таблица 6
| B1 | B2 | B3 | B4 | B5 | Запасы, ai | А1 | 14 | 8 | 17 | 5 | (110)3 | 120,10 | А2 | 21 | 10 | 7 | 11 | 6 | 180 | А3 | (70)3 | 5 | 8 | (125)4 | 9 | 230,160,35 | Потребности, bj | 70,0 | 120 | 105 | 125,0 | 110,0 | |
Ищем в таблице 6 минимальную стоимость – это ячейка (3,2), т.е. 3-я строка и
2-й столбец. Определяем минимум из запасов в 3-й строке и потребностей во 2-м
столбце. Он равен 35. Записываем в скобках в ячейку (3,2) 35 и вычеркиваем 3-
ю строку, а запасы 2-го столбца уменьшаем на 35 единиц, т.е. 120 - 35 = 85
ед.
Таблица 7
| B1 | B2 | B3 | B4 | B5 | Запасы, ai | А1 | 14 | 8 | 17 | 5 | (110)3 | 120,10 | А2 | 21 | 10 | 7 | 11 | 6 | 180 | А3 | (70)3 | (35)5 | 8 | (125)4 | 9 | 230,160,35,0 | Потребности, bj | 70,0 | 120,85 | 105 | 125,0 | 110,0 | |
Ищем в таблице 7 минимальную стоимость – это ячейка (2,3), т.е. 2-я строка и
3-й столбец. Определяем минимум из запасов во 2-й строке и потребностей в 3-м
столбце. Он равен 105. Записываем в скобках в ячейку (2,3) 105 и вычеркиваем
3-й столбец, а запасы 2-й строки уменьшаем на 105 единиц, т.е. 180 - 105 = 75
ед.
Таблица 8
| B1 | B2 | B3 | B4 | B5 | Запасы, ai | А1 | 14 | 8 | 17 | 5 | (110)3 | 120,10 | А2 | 21 | 10 | (105)7 | 11 | 6 | 180,75 | А3 | (70)3 | (35)5 | 8 | (125)4 | 9 | 230,160,35,0 | Потребности, bj | 70,0 | 120,85 | 105,0 | 125,0 | 110,0 | |
Вычеркиваем далее 2-й столбец и записываем в ячейку (1,2) 10, а в ячейку
(2,2) 75. В результате все запасы и потребности полностью израсходованы.
Таблица 9
| B1 | B2 | B3 | B4 | B5 | Запасы, ai | А1 | 14 | (10)8 | 17 | 5 | (110)3 | 120,10,0 | А2 | 21 | (75)10 | (105)7 | 11 | 6 | 180,75,0 | А3 | (70)3 | (35)5 | 8 | (125)4 | 9 | 230,160,35,0 | Потребности, bj | 70,0 | 120,85,0 | 105,0 | 125,0 | 110,0 | |
Таким образом, получен базисный план транспортной задачи закрытого типа:
 .
Проверим найденный базисный план на оптимальность методом потенциалов.
Запишем транспортную таблицу с опорным решением.
Таблица 10
| B1 | B2 | B3 | B4 | B5 | Запасы, ai | А1 | 14 | (10)8 | 17 | 5 | (110)3 | 120 | А2 | 21 | (75)10 | (105)7 | 11 | 6 | 180 | А3 | (70)3 | (35)5 | 8 | (125)4 | 9 | 230 | Потребности, bj | 70 | 120 | 105 | 125 | 110 | |
В методе потенциалов каждой i-й строке и j-му столбцу
транспортной таблицы ставятся в соответствие числа (потенциалы) ui
и vj. Для каждой базисной переменной xij
потенциалы удовлетворяют уравнению:
ui + vj = cij.
В рассматриваемой задаче имеем 8 неизвестных переменных (потенциалов) и 7
уравнений, соответствующих семи базисным переменным. Чтобы найти значения
потенциалов из системы уравнений для базисных переменных присвоим одному из
потенциалов произвольное значение, и затем последовательно вычислим значения
остальных потенциалов. Возьмем для определенности u1 = 0.
Имеем таблицу:
Таблица 11
| Базисные переменные | Уравнения относительно потенциалов | Решение | x12 | u1 + v2 = 8 | u1 = 0 Þ v2 = 8 | x15 | u1 + v5 = 3 | u1 = 0 Þ v5 = 3 | x22 | u2 + v2 = 10 | v2 = 8 Þ u2 = 2 | x23 | u2 + v3 = 7 | u2 = 2 Þ v3 = 5 | x31 | u3 + v1 = 3 | u3 = -3 Þ v1 = 0 | x32 | u3 + v2 = 5 | v2 = 8 Þ u3 = -3 | x34 | u3 + v4 = 4 | u3 = -3Þ v4 = 7 |
Далее, используя вычисленные значения потенциалов, для каждой свободной
переменной вычислим величины ui + vj -
cij. Результаты приведены в таблице 12.
Таблица 12
| Свободные переменные | Значения ui + vj - cij | x11 | u1 + v1 - c11 = 0 + 0 - 14 = -14 | x13 | u1 + v3 - c13 = 0 + 3 - 17 = -14 | x14 | u1 + v4 - c14 = 0 + 7 - 5 = 2 | x21 | u2 + v1 - c21 = 2 + 0 - 21 = -19 | x24 | u2 + v4 - c24 = 2 + 7 - 11 = -2 | x25 | u2 + v5 - c25 = 2 + 3 - 6 = -1 | x33 | u3 + v3 - c33 = -3 + 5 - 8 = -6 | x35 | u3 + v5 - c35 = -3 + 5 - 9 = -7 |
Т.к. получили положительное значение ui + vj
- cij, то полученное решение не является оптимальным. Введем
в базис ту свободную переменную, у которой значение ui +
vj - cij является положительным. Это –
переменная x14. Строим для нее цикл из четного числа
переменных, все вершины которого (кроме самой этой переменной) находятся в
занятых клетках. Около свободной клетки цикла ставится знак (+), затем
поочередно проставляем знаки (-) и (+):
| (10)(-) | | (+) | (110) | | (75) | (105) | | | | (70) | (35)(+) | | (125)(-) | |
У вершин со знаком (-) выбираем минимальный груз, он равен 10. Прибавляем его
к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у
отрицательных вершин. Получаем новый цикл:
| | | (10) | (110) | | (75) | (105) | | | | (70) | (45) | | (115) | |
В результате имеем новое опорное решение:
 .
Проверим полученное решение на оптимальность. Определим потенциалы строк и
столбцов, считаем, для определенности u1 = 0. Имеем таблицу:
Таблица 13
| Базисные переменные | Уравнения относительно потенциалов | Решение | x14 | u1 + v4 = 5 | u1 = 0 Þ v4 = 5 | x15 | u1 + v5 = 3 | u1 = 0 Þ v5 = 3 | x22 | u2 + v2 = 10 | u2 = 4 Þ v2 = 6 | x23 | u2 + v3 = 7 | v5 = 3 Þ u2 = 4 | x31 | u3 + v1 = 3 | u3 = -1 Þ v1 = 4 | x32 | u3 + v2 = 5 | v2 = 6 Þ u3 = -1 | x34 | u3 + v4 = 4 | u3 = -1Þ v4 = 5 |
Страницы: 1, 2, 3, 4
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
