- •Построение моделей. Типы моделей
- •Выпуклые множества. Выпуклые функции. Критерии выпуклости функции
- •Постановка задачи оптимизации. Необходимое условие экстремума. Достаточное условие экстремума
- •Определение поверхности (линии) уровня и направления наискорейшего роста целевой функции. Критерий оптимальности
- •Задачи на условный экстремум. Метод множителей Лагранжа. Необходимое условие существования условного локального экстремума функции
- •Задача выпуклого программирования. Теорема Куна-Таккера
- •Постановка задач линейного программирования. Формы записи злп
- •Предмет исследования операций
- •Основное неравенство теории двойственности. Основная теорема двойственности
- •Правило нахождения разрешающего элемента при использовании симплекс-метода. Экономическая интерпретация выбора направляющей строки и столбца
- •Правило построения новой симплексной таблицы. Как выписывается улучшенное решение из новой таблицы
- •Принятие решений в условиях неопределенности. Критерий Лапласа. Критерий Гурвица
- •Двойственность задач линейного программирования. Правило построения двойственной задачи
- •Двойственный симплекс-метод
- •Алгоритм двойственного симплекс-метода
- •Задача коммивояжера. Метод ветвей и границ
- •Задача о назначениях. Венгерский метод
- •Метод Гомори
- •Задачи нахождения кратчайшего пути. Алгоритм Дейкстры
- •Сетевые модели
- •Метод потенциалов
- •Задача нахождения кратчайшего пути. Алгоритм Флойда
- •Математическая постановка и разрешимость транспортной задачи
- •Метод северо-западного угла
- •Метод минимального элемента
- •Задача о максимальном потоке. Алгоритм нахождения максимального потока
- •Перебор разрезов
- •Экономическая интерпретация двойственных переменных. Анализ устойчивости двойственных оценок
- •Метод искусственного базиса (модифицированный симплекс метод)
- •2.1 Положительность строки m
- •2.2 Положительность строки f
Метод северо-западного угла
Составление первоначального плана перевозок начнем с перевозки запасов поставщика A1. Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя Bi, затем B2 и так далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1; 1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика A1 не окажется меньше заказа очередного потребителя. Для выполнения этого заказа используем остатки запаса первого поставщика, а недостающую часть добавим из запасов поставщика A2, то есть переместимся на следующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика A2, затем A3 и так далее.
Пример:
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
1 |
2 |
3 |
Запасы |
1 |
1 |
2 |
3 |
100 |
2 |
4 |
5 |
6 |
150 |
3 |
7 |
8 |
9 |
50 |
Потребности |
80 |
120 |
100 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100 + 150 + 50 = 300
∑b = 80 + 120 + 100 = 300
Этап I. Поиск первого опорного плана.Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
|
1 |
2 |
3 |
Запасы |
1 |
1[80] |
2[20] |
3 |
100 |
2 |
4 |
5[100] |
6[50] |
150 |
3 |
7 |
8 |
9[50] |
50 |
Потребности |
80 |
120 |
100 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
|
v1=1 |
v2=2 |
v3=3 |
u1=0 |
1[80] |
2[20] |
3 |
u2=3 |
4 |
5[100] |
6[50] |
u3=6 |
7 |
8 |
9[50] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. Минимальные затраты составят: F(x) = 1*80 + 2*20 + 5*100 + 6*50 + 9*50 = 1370
