Решение транспортной задачи методом потенциалов
Любой опорный план ТЗ должен удовлетворять двум условиям:
1. Количество занятых клеток должно равняться числу m+n-1
2. Опорный план должен быть ацикличным, т.е. в таблице с опорным планом невозможно построить замкнутую ломаную линию вершины которой располагались бы в занятых клетках, а звенья вдоль строк или столбцов.
Теорема
Если для некоторого опорного плана
x*=(xij) i=1,m; j=1,n существуют такие числа
U1, … Um,
V1, … Vm, что
(3)
(4)
То x*=(xij) – оптимальный опорный план ТЗ
Числа Ui и Vj называются потенциалами соответственно пунктов отправления и пунктов назначения. Данная теорема позволяет определить алгоритм поиска оптимального решения ТЗ.
Пусть построен опорный план ТЗ. Для каждого пункта отправления и назначения определяются потенциалы Ui и Vj. Эти числа определяются из системы линейных уравнений (3). Поскольку достаточно найти любое частное решение (3), то одну из неизвестных можно приравнять к произвольному числу, например Ui = 0 и найти из (3) остальные неизвестные. После того как найдены все потенциалы, для каждой из свободных клеток определяются числа,
которые называются оценками свободных клеток.
Если среди оценок нет отрицательных, что соответствует условию (4), то найденный опорный план будет оптимальным.
Если среди этих оценок есть отрицательные, то план не является оптимальным и необходимо перейти к новому опорному плану. Для этого выбирается клетка с наибольшей по абсолютной величине отрицательной разностью Sij и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Причем, одно звено каждой вершины находится в строке, другое в столбце.
Переход к новому опорному плану осуществляется путем изменения грузов в пределах клеток по следующему алгоритму:
1. По вершинам цикла расставляются чередующиеся знаки «+» и «-», причем в свободную клетку цикла ставится «+»
2. Находим минимальной значение груза в ячейках цикла имеющих знак «-» и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус - вычитаем, где плюс - прибавляем).
Получем новый опорный план и снова вычисляем значения потенциалов и разности Sij.
2. Построить опорное решение методом «северо-западного» угла и методом минимального тарифа. Решить транспортную задачу методом потенциала для опорного плана, полученного при решении методом «северо-западного» угла.
| 1ai/bi | ||||
| [4 | [5 | [7 | [2 | |
| [9 | [8 | [7 | [9 | |
| [4 | [6 | [8 | [7 |
| 2ai/bi | ||||
| [4 | [8 | [5 | [7 | |
| [7 | [6 | [4 | [6 | |
| [5 | [9 | [8 | [3 |
| 3ai/bi | ||||
| [7 | [4 | [8 | [6 | |
| [3 | [9 | [5 | [4 | |
| [8 | [7 | [4 | [5 |
| 4ai/bi | ||||
| [5 | [6 | [6 | [4 | |
| [7 | [5 | [6 | [3 | |
| [4 | [5 | [9 | [3 |
| 5ai/bi | ||||
| [8 | [7 | [6 | [7 | |
| [4 | [8 | [3 | [7 | |
| [5 | [6 | [4 | [5 |
| 6ai/bi | ||||
| [7 | [5 | [6 | [5 | |
| [4 | [3 | [5 | [6 | |
| [8 | [7 | [5 | [7 |
| 7ai/bi | ||||
| [8 | [7 | [4 | [4 | |
| [6 | [9 | [6 | [8 | |
| [5 | [8 | [5 | [6 |
| 8ai/bi | ||||
| [7 | [6 | [8 | [7 | |
| [6 | [7 | [5 | [9 | |
| [7 | [6 | [6 | [9 |
| 9ai/bi | ||||
| [7 | [6 | [5 | [8 | |
| [9 | [8 | [7 | [7 | |
| [8 | [9 | [7 | [8 |
| 10ai/bi | ||||
| [4 | [6 | [7 | [6 | |
| [5 | [3 | [4 | [5 | |
| [4 | [5 | [8 | [9 |
| 11ai/bi | ||||
| [8 | [4 | [7 | [3 | |
| [6 | [8 | [6 | [8 | |
| [5 | [4 | [5 | [6 |
| 12ai/bi | ||||
| [7 | [6 | [8 | [7 | |
| [4 | [5 | [6 | [3 | |
| [8 | [6 | [7 | [9 |
| 13ai/bi | ||||
| [5 | [6 | [4 | [3 | |
| [8 | [4 | [9 | [5 | |
| [7 | [5 | [7 | [4 |
| 14ai/bi | ||||
| [8 | [4 | [7 | [3 | |
| [6 | [8 | [6 | [8 | |
| [5 | [4 | [5 | [6 |
| 16ai/bi | ||||
| [8 | [9 | [7 | [8 | |
| [7 | [6 | [8 | [7 | |
| [6 | [5 | [6 | [4 |
| 15ai/bi | ||||
| [9 | [6 | [7 | [5 | |
| [8 | [7 | [9 | [6 | |
| [7 | [8 | [6 | [7 |
| 17ai/bi | ||||
| [4 | [3 | [2 | [3 | |
| [5 | [6 | [4 | [5 | |
| [6 | [5 | [2 | [3 |
| 18ai/bi | ||||
| [8 | [7 | [8 | [9 | |
| [6 | [6 | [5 | [7 | |
| [8 | [7 | [6 | [8 |
| 19ai/bi | ||||
| [8 | [5 | [7 | [7 | |
| [6 | [6 | [8 | [7 | |
| [7 | [5 | [6 | [6 |
| 20ai/bi | ||||
| [7 | [8 | [6 | [3 | |
| [9 | [7 | [5 | [8 | |
| [6 | [7 | [4 | [6 |
| 21ai/bi | ||||
| [5 | [8 | [3 | [5 | |
| [5 | [4 | [6 | [4 | |
| [4 | [7 | [6 | [5 |
| 22ai/bi | ||||
| [7 | [7 | [6 | [5 | |
| [9 | [8 | [9 | [7 | |
| [8 | [6 | [7 | [8 |
| 23ai/bi | ||||
| [6 | [9 | [8 | [7 | |
| [8 | [7 | [6 | [8 | |
| [7 | [5 | [6 | [8 |
| 24ai/bi | ||||
| [7 | [8 | [6 | [7 | |
| [8 | [9 | [7 | [8 | |
| [6 | [7 | [6 | [7 |
| 25ai/bi | ||||
| [5 | [4 | [6 | [3 | |
| [7 | [8 | [9 | [6 | |
| [6 | [7 | [4 | [5 |
| 26ai/bi | ||||
| [4 | [5 | [4 | [6 | |
| [3 | [4 | [5 | [2 | |
| [6 | [3 | [6 | [5 |
| 27ai/bi | ||||
| [5 | [6 | [7 | [6 | |
| [8 | [8 | [7 | [9 | |
| [7 | [4 | [6 | [7 |
| 28ai/bi | ||||
| [8 | [8 | [7 | [8 | |
| [6 | [7 | [9 | [8 | |
| [7 | [8 | [6 | [7 |
| 29ai/bi | ||||
| [7 | [8 | [7 | [9 | |
| [8 | [7 | [6 | [8 | |
| [6 | [8 | [5 | [6 |
| 30ai/bi | ||||
| [7 | [8 | [7 | [9 | |
| [8 | [6 | [8 | [7 | |
| [7 | [8 | [7 | [6 |
3. Решить транспортную задачу на сети
| 10n |
| 20n |
| -10n |
| -9n |
| -5n |
| -7n |
| n |
n – номер варианта
Контрольные вопросы
1. Что такое транспортная задача?
2. Что такое целевая функция и система ограничений?
3. Какие методы линейного программирования для решения транспортной задачи вы знаете?
4. В чем суть метода минимального тарифа?
ПРАКТИЧЕСКАЯ РАБОТА №2
Выбор оптимального варианта построения АИС небольшой фирмы
Цель работы:приобретение практических навыков по построению разных вариантов АИС небольшой фирмы и выбора из них оптимального.
Исходные данные
Условие задачи: На фирме работают три человека: генеральный директор, коммерческий директор, бухгалтер. Осуществляется два направления деятельности: оптовая торговля книгами, оптовая торговля канцелярскими товарами. Существует неограниченный доступ в Интернет. У каждого сотрудника свой персональный компьютер. Бухгалтерия учет предприятия полностью автоматизирован. Поиск поставщиков и покупателей ведется в сети Интернет, а связь с ними осуществляется частично через Интернет, частично с использованием обычных средств связи (почта, телефон, факс).
Ход работы:
1. Выделите информационные потоки предприятия
2. Предложите варианты построения АИС для представленной фирмы
3. Опишите преимущества и недостатки выбранного вами варианта построения АИС
Контрольные вопросы
1. Что такое АИС?
2. Какие типы АИС вы знаете?
3. Что такое обеспечивающая часть АИС?
4. Что такое функциональная часть АИС?
ПРАКТИЧЕСКАЯ РАБОТА №3.