- •1. Предмет и задачи курса. Экономико-математическая модель задачи линейного программирования. Пример.
- •2. Общая постановка задачи линейного программирования. Каноническая форма задачи линейного программирования.
- •3. Система линейных алгебраических уравнений (слау). Метод Гаусса. Пример.
- •4. Матрицы.
- •5. Обратная матрица.
- •6. Неопределенная система лау. Базисные.
- •7. Множества. Выпуклые линейные комбинации.
- •8. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.
- •9. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
- •10. Теорема об экстремальном значении целевой функции.
- •13. Нахождение исходного опорного решения.
- •14. Симплексный метод.
- •16. Приращение целевой функции
- •17, 18. Критерии оптимальности
- •19. Метод невязок.
- •20. Двойственные задачи.
- •24. Теоремы двойственности. Основное неравенство двойственности.
- •28. Теорема о ранге матрицы коэффициентов тз
- •29. Нахождение исходного опорного решения транспортной задачи
- •30. Переход к новому опорному решению тз
- •32. Метод потенциалов.
- •33. Теорема об эквивалентных преобразованиях матрицы затрат.
- •35. Оценка свободной клетки.
- •36. Критерий оптимальности. Переход к оценочной матрице.
- •37.Открытая модель транспортной задачи.
- •38. Распределительный метод
- •39. Постановка задачи цп.
- •40.Метод Гомори.
- •41. Понятие об игровых моделях
- •42. Приведение экономических задач к теоретико-игровой форме.
- •43. Парная конечная игра. Платежная матрица. Maxmin/minmax стратегии.
30. Переход к новому опорному решению тз
В ТЗ переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок. Для определения количества единиц груза, подлежащих распределению, отмечаем знаком + клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало p+q, поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком +, находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл и, начиная движения от клетки, отмеченной знаком +, поочередно проставляем знаки + и -. Затем находим ג=minxij, где xij – перевозки, стоящие в вершинах цикла, отмеченных знаком -. Величина ג определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение ג записываем в незанятую клетку, отмеченную знаком +, двигаясь по циклу, вычитаем ג из объемов перевозок, находящихся в клетках, отмеченных знаком +. Если ג соответствуют несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было p+q-1.
Проверяем полученный план на оптимальность. Ищем потенциалы последней матрицы. Так как отрицательных оценок нет, построенный план является оптимальным. Если полученный план окажется неоптимальным, то следует выполнить перечисленные вычисления еще раз. Процесс выполняют до тех пор, пока все незанятые клетки не будут удовлетворять условию оптимальности.
Циклы
Циклом называется набор клеток, вида: (L1;K1);( L1;K2);( L2;K2)…( Ls;K1) или (L1;K1);( L2;K1);( L2;K2)…( L1;Kl), в которых две и только две соседние клетки расположены в распределительной таблице, причем последняя клетка находится в том же столбце или той же строке, что и первая. Графически циклу соответствует замкнутая ломанная линия с прямыми углами. Допустимые решения ТЗ являются опорными, лишь в том случае, если из занятых этим решением клеток нельзя образовать ни одного цикла. Если в распределительной таблице содержится опорное решение, то для каждой свободной клетки можно образовать один цикл, содержащий данную свободную и некоторую часть занятых клеток.
Все вершины цикла кроме одной находятся в занятых клетках; углы прямые, число вершин четное. никакие 3 соседние клетки не могут быть в одной строке или в одном столбце. Около свободной клетки цикла ставится знак (+), затем поочередно проставляются знаки(-)и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящих у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-).В результате перераспределения груза получается новое опорное решение
32. Метод потенциалов.
1. Строят исходное опорное решение (план).
2. Выписывают матрицу затрат С и находят потенциалы Ui и Vk по формуле Cik+Ui+Vk=0 для все занятых клеток. Один из потенциалов полагают равным произвольнному числу (обычно полагают Ui=0 потенциал в троке или в столбце с наибольшим количеством занятых клеток).
3. Переходят к оценочной матрице С’, элементы которой находят по формуле C’={Cik}, Cik’=Cik+Ui+Vk.
4. Если все оценки Δst≥0 для свободных клеток, то полученное решение оптимально и найдено.
5. Если хотя бы одна оценка Δst<=0, то для клетки с максимальной по абсолютной величине отрицательной оценкой строят цикл и переходят к новому опорному решению. Процесс продолжается до тех пор, пока не будет получено решение, для которого все оценки свободных клеток будут ≥0.