- •Системный анализ и исследование операций
- •В 2 частях
- •Часть II Гомель 2005
- •Содержание
- •Введение
- •Практическая работа n1 транспортные задачи
- •Решение транспортной задачи
- •Метод северо-западного угла
- •Метод наименьшей стоимости
- •Метод Фогеля
- •Оптимизация плана транспортной задачи
- •Распределительный метод
- •Метод потенциалов
- •Практическая работа n2 транспортная задача на min времени
- •Метод запрещённых клеток.
- •Практическая работа №3 задача о назначениях
- •Решение через нуль-базис
- •Практическая работа №4 определение кратчайшего маршрута
- •Определение кратчайшего пути на сети без циклов
- •Определение кратчайшего пути на сети с циклами
- •Практическая работа № 5 пропускная способность сети
- •Алгоритм нахождения максимального потока
- •Тестовый пример
- •Практическая работа №6 календарное планирование
- •Сетевое представление программы (сетевая модель)
- •Правила построения сетевой модели
- •Расчет сетевой модели
- •Определение критического пути
- •Определение резервов времени
- •Практическая работа №7 антагонистические игры
- •Чистые и смешанные стратегии
- •Упрощение игры
- •Игровые модели. Графоаналитический метод решения
- •Практическая работа №8 игровые модели. Решение методом итераций
- •Практическая работа №9 решение задач линейного программирования с помощью игровых моделей
- •Литература
- •Приложение
- •Давыдов владимир семёнович системный анализ и исследование операций Практическое пособие
- •Часть II в авторской редакции
- •246019, Г. Гомель, ул. Советская, 104
- •246019, Г. Гомель, ул. Советская, 104
Решение транспортной задачи
При решении транспортной задачи повторяются этапы реализации симплекс-алгоритма, однако способ проверки условий: оптимальности и допустимости видоизменяется.
Основные шаги алгоритма.
Шаг 1. Найти начальное допустимое решение.
Шаг 2. Выделить из числа небазисных переменных вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности, закончить вычисления; в противном случае перейти к шагу 3.
Шаг 3. Выбрать выводимую из базиса переменную (используя условие допустимости) из числа переменных текущего базиса; затем найти новое базисное решение. Вернуться к шагу 2.
Определение начального решения
Согласно общему определению транспортной модели необходимо ( = ), откуда следует, что одно уравнение оказывается зависимым, т. е. транспортная модель содержит только т+п-1 независимых уравнений. Таким образом, как и в симплекс-методе, начальное базисное допустимое решение должно иметь т+п-1 базисную переменную.
Начальное базисное допустимое решение легко получить из транспортной таблицы. Для этой цели используется один из приведенных ниже методов.
Сущность этих методов состоит в том, что опорный план находят последовательно за п+т-1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения (того, в столбце которого находится заполненная клетка), либо вывоз груза из одного из пунктов отправления (из того, в строке которого находится заполняемая клетка).
В первом случае временно исключают из рассмотрения столбец, содержащий заполненную на данном шаге клетку, и рассматривают задачу, таблица условий которой содержит на один столбец меньше, чем было перед этим шагом, но то же количество строк и соответственно измененные запасы груза в одном из пунктов отправления ( в том, за счет запаса которого была удовлетворена потребность в грузе пункта назначения на данном шаге ). Во втором случае временно исключают из рассмотрения строку, содержащую заполненную клетку, и считают, что таблица условий имеет на одну строку меньше при неизменном количестве столбцов и при соответствующем изменении потребности в грузе в пункте назначения, в столбце которого находится заполняемая клетка.
После того как проделаны т+п-2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (n+т-1)-й шаг и получают искомый опорный план. Следует заметить, что на некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-нибудь одно). Таким образом, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение п+т-1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.