|
|
| Контрольная: Транспортная задача |
Далее, используя вычисленные значения потенциалов, для каждой свободной
переменной вычислим величины ui + vj -
cij. Результаты приведены в таблице 14.
Таблица 14
| Свободные переменные | Значения ui + vj - cij | x11 | u1 + v1 - c11 = 0 + 4 - 14 = -10 | x12 | u1 + v2 - c12 = 0 + 4 - 8 = -4 | x13 | u1 + v3 - c13 = 0 + 5 - 17 = -12 | x21 | u2 + v1 - c21 = 3 + 4 - 21 = -14 | x24 | u2 + v4 - c24 = 3 + 6 - 11 = -2 | x25 | u2 + v5 - c25 = 3 + 5 - 6 = 2 | x33 | u3 + v3 - c33 = -1 + 4 - 8 = -5 | x35 | u3 + v5 - c35 = -1 + 3 - 9 = -7 |
Т.к. получили положительное значение ui + vj
- cij, то полученное решение не является оптимальным. Введем
в базис ту свободную переменную, у которой значение ui +
vj - cij является положительным. Это –
переменная x24. Строим для нее цикл из четного числа
переменных, все вершины которого (кроме самой этой переменной) находятся в
занятых клетках. Около свободной клетки цикла ставится знак (+), затем
поочередно проставляем знаки (-) и (+):
| | | (10) | (110) | | (75)(-) | (105) | (+) | | | (70) | (45)(+) | | (115)(-) | |
У вершин со знаком (-) выбираем минимальный груз, он равен 75. Прибавляем его
к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у
отрицательных вершин. Получаем новый цикл:
| | | (10) | (110) | | | (105) | (75) | | | (70) | (120) | | (40) | |
В результате имеем новое опорное решение:
 .
Проверим полученное решение на оптимальность. Определим потенциалы строк и
столбцов, считаем, для определенности u1 = 0. Имеем таблицу:
Таблица 15
| Базисные переменные | Уравнения относительно потенциалов | Решение | x14 | u1 + v4 = 5 | u1 = 0 Þ v4 = 5 | x15 | u1 + v5 = 3 | u1 = 0 Þ v5 = 3 | x23 | u2 + v3 = 7 | u2 = 6 Þ v3 = 1 | x24 | u2 + v4 = 11 | v4 = 5 Þ u2 = 6 | x31 | u3 + v1 = 3 | u3 = -1 Þ v1 = 4 | x32 | u3 + v2 = 5 | u3 = -1 Þ v2 = 6 | x34 | u3 + v4 = 4 | v4 = 5 Þ u3 = -1 |
Далее, используя вычисленные значения потенциалов, для каждой свободной
переменной вычислим величины ui + vj -
cij. Результаты приведены в таблице 14.
Таблица 16
| Свободные переменные | Значения ui + vj - cij | x11 | u1 + v1 - c11 = 0 + 4 - 14 = -10 | x12 | u1 + v2 - c12 = 0 + 6 - 8 = -2 | x13 | u1 + v3 - c13 = 0 + 1 - 17 = -16 | x21 | u2 + v1 - c21 = 6 + 4 - 21 = -11 | x22 | u2 + v2 - c22 = 6 + 6 - 10 = 2 | x25 | u2 + v5 - c25 = 6 + 3 - 6 = 3 | x33 | u3 + v3 - c33 = -1 + 1 - 8 = -8 | x35 | u3 + v5 - c35 = -1 + 3 - 9 = -7 |
Т.к. получили несколько положительных значений ui + v
j - cij, то полученное решение не является
оптимальным. Введем в базис ту свободную переменную, у которой значение u
i + vj - cij является
максимальным. Это – переменная x25. Строим для нее цикл из
четного числа переменных, все вершины которого (кроме самой этой переменной)
находятся в занятых клетках. Около свободной клетки цикла ставится знак (+),
затем поочередно проставляем знаки (-) и (+):
| | | (10)(+) | (110)(-) | | | (105) | (75)(-) | (+) | | (70) | (120) | | (40) | |
У вершин со знаком (-) выбираем минимальный груз, он равен 75. Прибавляем его
к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у
отрицательных вершин. Получаем новый цикл:
| | | (85) | (35) | | | (105) | | (75) | | (70) | (120) | | (40) | |
В результате имеем новое опорное решение:
 .
Проверим полученное решение на оптимальность. Определим потенциалы строк и
столбцов, считаем, для определенности u1 = 0. Имеем таблицу:
Таблица 17
| Базисные переменные | Уравнения относительно потенциалов | Решение | x14 | u1 + v4 = 5 | u1 = 0 Þ v4 = 5 | x15 | u1 + v5 = 3 | u1 = 0 Þ v5 = 3 | x23 | u2 + v3 = 7 | u2 = 3 Þ v3 = 4 | x25 | u2 + v5 = 6 | v5 = 3 Þ u2 = 3 | x31 | u3 + v1 = 3 | u3 = -1 Þ v1 = 4 | x32 | u3 + v2 = 5 | u3 = -1 Þ v2 = 6 | x34 | u3 + v4 = 4 | v4 = 5 Þ u3 = -1 |
Далее, используя вычисленные значения потенциалов, для каждой свободной
переменной вычислим величины ui + vj -
cij. Результаты приведены в таблице 14.
Таблица 18
| Свободные переменные | Значения ui + vj - cij | x11 | u1 + v1 - c11 = 0 + 4 - 14 = -10 | x12 | u1 + v2 - c12 = 0 + 6 - 8 = -2 | x13 | u1 + v3 - c13 = 0 + 4 - 17 = -13 | x21 | u2 + v1 - c21 = 3 + 4 - 21 = -14 | x22 | u2 + v2 - c22 = 3 + 6 - 10 = -1 | x24 | u2 + v4 - c24 = 3 + 5 - 11 = -3 | x33 | u3 + v3 - c33 = -1 + 4 - 8 = -5 | x35 | u3 + v5 - c35 = -1 + 3 - 9 = -7 |
Т.к. все среди значений ui + vj - cij нет положительных, то полученное решение
является оптимальным. Минимальные транспортные издержки при этом составят:
Список литературы
1. Дыхнов А.Е., Дягелец И.Д., Тумашев В.И. Математические методы исследования
экономики. Часть I. Оптимальное программирование. – Челябинск, УрСЭИ АТиСО,
1999.
2. Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико-математические
методы в планировании. – М.: Высшая школа, 1991.
3. Исследование операций в экономике/ Под ред. Н.Ш. Кремера. – М.: Банки и
биржи, ЮНИТИ, 1997.
4. Косоруков О.А., Мищенко А.В. Исследование операций. – М.: Экзамен, 2003.
5. Бережная Е.В., Бережной В.И. Математические методы моделирования
экономических систем. М.: Финансы и статистика, 2001.
Страницы: 1, 2, 3, 4
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
