- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Транспортные задачи по критерию времени
При осуществлении перевозок определяющим показателем могут быть не затраты, а время доставки. Характерными примерами являются чрезвычайные ситуации, перевозка раненых, скоропортящихся продуктов и т. п. В таких задачах главное – как можно быстрее доставить все грузы. Тогда вместо матрицы транспортных затрат дается матрица времени [tij], а критерий выражает время завершения всех перевозок:
где максимум берется по коммуникациям, на которых перевозки больше нуля. Предполагается, что перевозки между всеми пунктами начинаются одновременно и ведутся параллельно. Условия задачи записываются как и в случаях с критерием-затратами. Однако здесь критериальная функция нелинейна, что принципиально отличает эту задачу от ранее рассмотренных. В то же время она легко преобразуется к линейному виду, и решение задачи может быть получено любым универсальным методом линейного программирования. Один приближенный метод рассмотрен в разд. 5.5.▲
Для решения транспортных задач применяют специальные методы, которые учитывают их особенности и поэтому более эффективны, чем универсальные. К ним относятся распределительный метод, метод потенциалов, венгерский метод, метод Глейзала и др. Основными являются методы венгерский и потенциалов. Они применяются для решения задач как типа Т, так и Тd. Ниже рассматривается второй из них.
21. Построение начального плана перевозок т-задачи
Концепция метода потенциалов та же, что и в симплекс-методе. Оптимальное решение ищется путем последовательных переходов от одного базисного решения (опорного плана) к другому с лучшим значением критерия. Но все шаги алгоритма выполняются проще, чем в симплекс-методе. В то же время метод потенциалов имеет много общего с распределительным методом и в связи с этим его иногда называют модифицированным распределительным методом.
Сначала рассмотрим метод применительно к Т-задаче, а затем сделаем дополнения, позволяющие решать Тd-задачу.
5.2.1. Построение начального плана перевозок
Как было показано выше, размерность базисного решения или плана перевозок равна m+n-1, где m и n – число ПО и ПН сбалансированной задачи. Если задача открытая, то сначала ее необходимо сбалансировать.
Следует также иметь в виду, что в транспортных задачах вырожденность базисного решения встречается очень часто. В задаче заведомо будут вырожденные решения, если имеются такие неполные группы пунктов отправления и назначения, что суммарная возможность первых равна суммарной потребности вторых. Вырожденным может оказаться и начальное решение.
Для построения начального плана перевозок применяют правила северо-западного угла, минимального элемента и алгоритм Фогеля. Последний можно применять и как приближенный метод решения Т-задачи.
Здесь мы рассмотрим только первые два способа. Хотя по аналогии легко предложить и другие правила. При этом важно соблюдать принцип: очередной переменной, включаемой в план, присваивать максимально допустимое значение. Этим обеспечится построение базисного решения.
Правило северо-западного угла
Все исходные данные и переменные сбалансированной Т-задачи удобно представить в виде таблицы (табл. 5.1).
Построение плана начинается с северо-западной клетки таблицы, то есть первым определяется значение переменной X11.
Таблица 5.1
|
b1 |
b2 |
… |
bn |
|
C11 X11 |
C12 X12 |
… |
C1n X1n |
|
C21 X21 |
C22 X22 |
… |
C2n X2n |
… |
… |
… |
… |
… |
|
Cm1 Xm1 |
Cm2 Xm2 |
… |
Cmn Xmn |
Так как оно должно быть максимально допустимым, то
При этом обязательно выполнится одно из равенств (5.3), (5.4), что соответствует закрытию строки или столбца: переменные в остальных клетках строки или столбца будут равны нулю. Конкретнее, если X11=а1, то закрывается первая строка и X12=X13=…=X1n=0, а следующей базисной переменной будет X21. Из указанного выше принципа следует X21=min(a2, b1-a1). Если же окажется, что X11=b1, то закроется первый столбец и следующей базисной переменной станет X12=min(a1-b1, b2).
Весь процесс построения начального плана можно представить в виде следующего дерева решений.
Общее правило определения значения очередной базисной переменной: Xij=min(остаток от ai, остаток до bj). (5.13)
Из него следует, что на каждом шаге закрывается или строка, или столбец, а на последнем шаге при назначении Xmn закрываются одновременно m-я строка и n-й столбец (так как задача сбалансированная). Таким образом, число базисных переменных равно m+ n-1. Построение начального плана завершено.
Пример 5.1. Исходные данные и построение начального плана показано в табл. 5.2. Значения базисных переменных выделены красным (серым) цветом, а порядок движения по клеткам отражен стрелками. Этому плану соответствуют суммарные затраты L=1295.
Таблица 5.2
Поставщик |
Потребитель |
Запасы груза |
|||
B1 |
B2 |
B3 |
B4 |
||
A1 |
6 75 |
7 25 |
3 |
5 |
100 |
A2 |
1 |
2 55 |
5 60 |
6 35 |
150 |
A3 |
3 |
10 |
20 |
1 50 |
50 |
Потребность в грузе |
75 |
80 |
60 |
85 |
300 |