- •Формулировка задачи линейного программирования (злп) в общей (озлп), стандартной (сзлп) и канонической (кзлп) формах. Переход от одной формы записи к другой
- •Теорема об оптимальном решении кзлп и вершине области
- •Симплексный метод. Приведение злп к канонической форме. Балансовые переменные. Выбор разрешающего элемента.
- •Теорема о связи оптимальных значений функций прямой и двойственной задач.
- •Признак отсутствия допустимого решения для задачи двойственной данной.
- •Теорема о связи оптимальных решений прямой и двойственной задач (Первая теорема двойственности).
- •, 4. Координатами вектора градиента являются цены изделий. Мы можем менять цены, тогда градиент функции будет меняться, вследствие чего оптимальной может стать другая точка.
- •Постановка транспортной задачи. Необходимое и достаточное условие существования допустимого решения транспортной задачи.
- •Нахождение базисного решения методом северо-западного угла.
- •Нахождение базисного решения методом наименьшей стоимости
- •Алгоритм метода потенциалов
- •Понятие о максимине и минимаксе. Необходимое и достаточное условие существования равновесия в чистых стратегиях. Цена игры.
- •Определение смешанной стратегии. Математическое ожидание выигрыша первого игрока в случае смешанных стратегий. Определение точки равновесия в смешанных стратегиях.
- •Теорема о существовании точки равновесия в случае смешанных стратегий. Теорема о цене игры в случае применения одним из игроков чистых стратегий.
- •Связь решения матричной игры с задачей линейного программирования для первого (второго) игрока.
- •Сетевой проект. Резервы времени событий (вершин) и работ (ребер). Критическое время выполнения проекта. Критический путь.
Нахождение базисного решения методом северо-западного угла.
-
Берется самая верхняя левая клетка (, туда проставляется груз: . То есть либо вывезен весь первый ПО, либо полностью удовлетворен первый ПН.
а) Если полностью вывезен ПО, то вычеркиваем а1, вместо b1 пишем число . Из первого ПО больше ничего нельзя вывезти, а в первый ПН осталось привезти . Оставшиеся клетки в строке будут пустыми (не занятыми).
б) Если полностью удовлетворен ПН, то вычеркиваем b1, вместо а1 пишем число . В первый ПН ничего больше нельзя ввезти. Оставшиеся клетки в столбце будут пустыми (незанятыми).
Находим следующую самую северо-западную клетку.
В случае а) – это будет – вторая строка, первый столбец.
В случае б) – это будет – первый столбец, вторая строка.
Снова заполняем ее аналогичным образом.
На каждом этапе либо какой-то ПО вывозится полностью, либо какой-то ПН удовлетворяется полностью.
Если на каком-то этапе (кроме последнего) какой-то ПО вывезен полностью И ПН удовлетворен полностью (одновременно), то в одном из пунктов груз вычеркивается, а в другом ставится 0 (либо в соответствующую строку, либо в соответствующий столбец). Такое решение является вырожденным, так как базисная переменная равна 0.
На последнем этапе все ПО вывезены и все ПН удовлетворены.
Нахождение базисного решения методом наименьшей стоимости
-
Находится клетка с наименьшей стоимостью перевозки. Туда ставится максимально возможный груз ().
-
Затем находится следующая клетка с наименьшей стоимостью – заполняется аналогично.
Так же как и методе северо-западного угла, если на каком-то этапе одновременно вычеркивается и ПО, и ПН, то ставится 0 – вырожденное решение.
Если при нахождении некоторого базисного решения методом наименьшей стоимости есть несколько клеток с наименьшей стоимостью, выбрать ту, куда можно привезти больше всего груза.
-
Определение потенциалов и оценок пустых (незанятых) клеток. Признак оптимальности базисного решения. Признак существования альтернативного решения; вырожденное решение.
Проверка решения на оптимальность может быть выполнена, например, методом потенциалов.
Метод потенциалов требует перехода к двойственной задаче. Потенциалы и являются переменными для двойственной задачи.
Прямая |
Двойственная |
Каждое - входит в ограничение дважды: для ПО и для ПН. |
могут принимать любое значение. |
Идея проверки на оптимальность заключается в следующем: нужно решить систему уравнений, которая возникает из неравенств соответствующих базисных переменных. Затем проверить, выполняется ли для найденных потенциалов неравенство в нужную сторону для свободных переменных.
Если неравенство для свободных переменных выполняется, то решение оптимальное. Если не выполняется – строить новое решение и проверять на оптимальность его.
Замечания:
-
Число уравнений в системе m+n-1, т.к. столько базисных переменных; Число потенциалов=m+n. Но это не затруднит проверку на оптимальность: один из потенциалов выбираем произвольно (обычно u1=0), тогда остальные будут найдены однозначно.
-
Даже если какая-то базисная переменная равна 0 (т.е. вырожденное решение), то все равно соответствующее ограничение задается в виде равенства.
-
Произвольный выбор потенциала не влияет на оценки свободных переменных.
-
Если какая-то оценка свободной переменной равна 0, то это признак альтернативного решения.
-
Если среди оценок свободных клеток есть отрицательные, то решение не оптимальное
-
Оценки – полные аналоги оценок симплекс-таблицы, которые стоят в индексной строке.