- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
Применим метод декомпозиции к Т-задаче:
(6.33)
(6.34)
(6.35)
Хij0. (6.36)
Использование этого метода целесообразно, если m<<n или m>>n. Оба варианта решаются идентично. Они отличаются только распределением условий между основной и вспомогательной задачами.
Рассмотрим случай, когда m<<n. Тогдо основная задача формируется по условиям пунктов отправления. Следовательно, множество D0 описывается ограничениями (6.34), а D1 – условиями (6.35) и (6.36).
Очевидно, что множество D1 представляет собой выпуклый многогранник (ограниченность вытекает из условий). Поэтому, как и в общем случае, любую точку в D1 можно представить в виде линейной комбинации его вершин:
(6.37)
Zv=1; (6.38)
Zv 0, (6.39)
где Xvij – координаты v-ой вершины.
Подставим (6.37) в (6.33) и (6.34):
.
Введем обозначения:
(6.40)
(6.41)
Тогда основная задача запишется в виде
(6.42)
6.43)
(6.44)
Zv 0. (6.45)
Для сбалансированной задачи условие (10) выполняется автоматически. Действительно, суммируя (6.43) и используя подстановки (6.41) и (6.35), получаем
в левой части
в правой части Таким образом,
откуда для сбалансированной задачи следует
Поэтому при решении основной задачи условие (6.44) из модели исключается.
Для определения статуса текущего базисного решения основной задачи необходимы относительные оценки. Как и в предыдущем разделе, нахождение оценок связано с решением вспомогательной задачи. Для построения вспомогательной задачи сделаем ряд преобразований:
v= TPv - v =
Так как основная задача решается на минимум, то оптимальному статусу соответствуют неположительные оценки. Поэтому нужно искать максимальную оценку. Если она окажется не больше нуля, то все оценки неположительны и признак оптимальности выполнился. В противном случае необходимо продолжить решение основной задачи.
Значит, задача ставится так:
Вместо поиска максимума на дискретном множестве вершин перейдем к эквивалентной задаче поиска на всем непрерывном множестве D1:
(6.46)
(6.47)
Xij 0. (6.48)
Эта задача и является вспомогательной. Очевидно, что в оптимальном решении этой задачи Теперь остается выяснить, как найти его.
Вспомогательная задача включает одну группу условий (6.47). Раньше было показано, что каждая переменная входит в такие условия только один раз. Поэтому равенства (6.47) оказываются независимыми и, следовательно, вспомогательная задача распадается на n простейших независимых задач, каждая из которых имеет всего одно условие:
(6.49)
(6.50)
Xij 0. (6.51)
Критерий вспомогательной задачи равен сумме критериев этих задач:
(6.52)
Оптимальное решение задачи (6.49)-(6.51), как линейной, находится на границе. При этом только одна переменная не равна нулю (базис имеет размерность 1). Поэтому ее решение состоит в определении максимального коэффициета в критерии (6.49). Пусть максимум достигается на индексе i*, то есть
Тогда имеем следующее решение задачи (6.49)-(6.51):
Xvi*j =bj, Xvij=0, i, ii*, (6.53)
и максимальная оценка определится как
.
Если L*всп 0, то положительных оценок нет и текущее решение основной задачи будет оптимальным.
При L*всп > 0 начинается новая итерация:
1. пo (6.41) и (6.40) находим Рv и v;
2. вычисляем элементы направляющего столбца как коэффициенты разложения вектора Рv по текущему базису:
v=P-1BPv;
3. проводим симплекс-преобразование основной задачи, в результате которого получаем новое решение и новую обратную матрицу;
4. вычисляем T=TBP-1B;
5. решаем вспомогательную задачу: вычисляем разности , находим оптимальные решения n задач (6.49)-(6.51) и максимальную оценку основной задачи.
Из рассмотренной вычислительной схемы следует, что эффективность метода тем выше, чем сильнее неравенство m<<n или m>>n.
Пример.
Решим транспортную задачу с двумя пунктами отправления и четырьмя пунктами назначения:
bi ai |
8 |
4 |
10 |
8 |
10 |
2 |
5 |
1 |
4 |
20 |
1 |
3 |
4 |
2 |
Числа в ячейках таблицы - затраты на перевозки Cij.
Исходная модель задачи:
L = CijXij min
(6.54)
(6.55)
Координирующая задача формируется по условиям (6.54):
Zv0.
Для построения начального решения вводим искусственные переменные:
и модифицируем критерий
Составим начальную таблицу координирующей задачи:
v |
Базисные перемен. |
P0 |
Pn+1 |
Pn+2 |
M |
Zn+1 |
10 |
1 |
0 |
M |
Zn+2 |
20 |
0 |
1 |
Т |
M |
M |
В последней строке значения i получены умножением первого столбца на столбцы Pn+i.
Решение вспомогательной задачи представляем в таблице:
bj |
8 |
4 |
10 |
8 |
1-C1j |
M-2 |
M-5 |
M-1 |
M-4 |
2-C2j |
M-1 |
M-3 |
M-4 |
M-2 |
v=1 |
X121=8 |
X122=4 |
X113=10 |
X124=8 |
Значения переменных в последней строке таблицы получены согласно (6.53). Например, при j=1 максимальная разность равна M-1, поэтому X121=b1= 8. Клетки с максимальными разностями выделены цветом фона. Вычисляем значение критерия по формуле (6.46):
[(M-1)*8 + (M-3)*4 + (M-1)*10 + (M-2)*8] > 0.
Так как признак оптимальности не выполняется, переходим к итерациям. Находим 1 согласно (6.40):
1=1*8 + 3*4 + 1*10 + 2*8 = 46.
Вычисляем компоненты вектора Р1:
Р11= X113=10;
P21= X121+ X122+ X124= 8+4+8 = 20.
Следовательно, . Находим его разложение по начальному базису:
.
Добавляем столбец P1 с элементами 1 в начальную таблицу в качестве направляющего столбца:
v |
Базисные перемен. |
P0 |
Pn+1 |
Pn+2 |
P1 |
|
M |
Zn+1 |
10 |
1 |
0 |
10 |
1 |
M |
Zn+2 |
20 |
0 |
1 |
20 |
1 |
Т |
M |
M |
|
В
v
Баз.
P0
Pn+1
Pn+2
46
Z1
1
0,1
0
M
Zn+2
0
-2
1
Т
-2M+4,6
M
Для выяснения статуса этого решения снова находим максимальную оценку основной задачи, решая вспомогательную задачу:
О
bj
8
4
10
8
1-C1j
2,6-2M
-0,4-2M
3,6-2M
0,6-2M
2-C2j
M-1
M-3
M-4
M-2
v=2
X221=8
X222=4
X223=10
X224=8
Вычисляем коэффициент критерия при Z2:
2=1*8 + 3*4 + 4*10 + 2*8 = 8+12+40+16 = 76.
Определяем компоненты вектора Р2:
Р12=0, P22= 8+4+10+8 = 30
Имея , находим элементы направляющего столбца
и
v
Баз.
P0
Pn+1
Pn+2
P2
46
Z1
1
0,1
0
0
-
M
Zn+2
0
-2
1
30
0
Т
-2M+4,6
M
В
v
Баз
P0
Pn+1
Pn+2
46
Z1
1
0,1
0
76
Z2
0
-1/15
1/30
Т
-7/15
38/15
С
bj
8
4
10
8
1-C1j
-37/15
-82/15
-22/15
-67/15
2-C2j
23/15
-7/15
-22/15
8/15
v=3
X321=8
X322=4
X313=10
X324=8
Критерий этой заачи L3всп =(23/15)*8–(7/15)*4–(22/15)*10+(8/15)*8=0. Следовательно, получено оптимальное решение основной задачи: Z*1=1, Z*2=0, L* = 46*1 + 76*0 = 46.
Находим значения исходных переменных по формуле (6.37), которая для нашей задачи принимает вид:
Таким образом, получено следующее оптимальное решение исходной задачи: X*21 = 8, X*22 = 4, X*13 = 10, X*24 = 8.
Проверка: L = CijXij=1*8 + 3*4 + 1*10 + 2*8=46. Это значение совпадает с вычисленным через переменные Zi.