- •31.32. Сетевая тз: улучшение базисного потока(итерация).
- •33. Построение начального базисного потока.
- •34. Матричная тз: постановка з-чи, теорема сущ-ния, транспортная таблица.
- •35. Матричная тз: построение нач. Базисного плана, метод сев-зап. Угла.
- •36. Матричная тз: метод потенциалов, модели тз.
- •37. Выпуклые множества и их свойства. Выпуклая оболочка множества
- •38. Выпуклые функции и их свойства. Выпуклая оболочка функции
- •39 Задача выпуклого программирования (вп). Функция Лагранжа (л), седловая точка функции Лагранжа. Необходимое условие оптимальности.
- •40. Гладкие задачи выпуклого программирования. Необходимое условие оптимальности для задачи с регулярным множеством планов.
35. Матричная тз: построение нач. Базисного плана, метод сев-зап. Угла.
Метод сев-зап-ого угла: выбираем клетку (1,1), перевозку в этой клетке полагаем min (a1,b1). Пример: 1) пусть x11=a1<b1, из таблицы вычеркиваем 1 строку мысленно. , в новой таблице опять ищем сев-зап-ый угол; 2) пусть x11=a1>b1, . Вычеркнем столбец. Через m+n-1 шагов останется не вычеркнута либо строка, либо столбец, но будет заполнена m+n-1 клетка. Они образуют базисное мн-во. Метод миним-ого элемента: на 1-ом шаге выбирается клетка с миним-ой стоимостью перевозки (i1,j1). По строке ai1 и потребление bj1. Выбираем min(ai1, bj1). Если xi1j1=ai1, то вычеркиваем строку с номером i1. . Если xi1j1=bj1, то вычеркиваем столбец с номером j1. Метод Фогеля: для каждой строки находим миним-ое значение стоимости, среди остальных значений стоимости снова находим миним-ое значении. Из второго значение вычитаем первое, полученное чило наз-ем штрафом. Аналогично вычисляем штраф в каждом столбце. Выделяем строку или столбец с маким-ым штрафом. В выделенной строке или столбце находим клетку с миним-ой стоимостью. Определяем в ней перевозку по те же правилам, что и в пред-щих методах с последующим вычеркиванием столбца или строки. Если в выбранной строке имеются клетки с одинаковой миним-ой стоимостью, то выбираем клетку из того столбца, где наибольший штраф. Для уменьшенной таблицы пересчитывают штрафы и повторяют выше указанные действия. Использую метод Фогеля для построения начального базисного плана в том же примере.
36. Матричная тз: метод потенциалов, модели тз.
Пусть на сети S={I, U} задан баз. поток которому соответствует дерево ={I, }
Вычисляем потенциалы вершин из ур-ий (при ручном счете берут вершину, которой инцендентна наибольшему количеству дуг)
Вычисляем оценки небазисных дуг согласно правилу
Проверяем выполнение условий . Если они выполняются, то текущий поток оптимальный, иначе переходим к 4.
Фиксируем дугу ( ) , для которой . Выбор этой дуги м/т быть произвольный, если таких дуг несколько. При ручном счёте обычно выбирают дугу с мин значением.
Строим цикл по дугам ( ) и дугам дерева, т е ( ) (согласно лемме: если – дерево сети S и ( ) то частичная сеть содержит ровно один цикл => цикл будет единственным) и фиксируем направление по дуге ( ).
Если все дуги в цикле прямые, то решение задачи останавливается: целевая функция не ограничена снизу.
В противном случаи определяем ( ) – циркуляцию со значением , где находится по правилу : мы находим величину, на которую м/о максим изменить дуговой поток, т е , на обратных дугах .
Фиксируем дугу ( ) на котрой достигается , т е .
Вычисляем дуговой поток по правилам :
Формируем новое базисное множество дуг следующим образом: из удаляем дугу ( ) и получаем: =( ), S={I, }
в совокупности с яв-ся потоком стоимость которого на величину меньше х.
Def. Переход от базисного потока х к баз потоку наз-ся итерация метода потенциалов.
Метод потенциалов конечен (за конечное число итераций получается оптим баз план), если все баз потоки не вырожденные.
Модели ТЗ:1)закрытая модель- выполняется условие общего баланса ( т е совокупный спрос равен совокупному предложению)
2)открытая- не выполняется условие общего баланса. Открытую модель МТЗ сводят к закрытой. Если , это означает что спрос превышает предложение. Введём дополнительного фиктивного поставщика с объёмом поставок и стоимостью перевозок . Величина в оптимальном плане перевозок означает объем недопоставки потребителю . В случае (предложение привышает спрос) вводим фиктивного потребителя с
объёмом потребления и стоимостью перевозок . Величина в
оптимальном плане перевозок означает объем продукции, оставшейся нереализованной (на складе) у поставщика .
3) задача запрещения перевозок – в этом случаи стоимость перевозки делаю очень большой, чтобы по ней ничего не перевозить
4)задача обязательной перевозки по указанному маршруту
5)если требуется перевезти груз не более или не менее заданного объёма