- •Предмет «Математическое программирование», общая постановка задачи, различные его разделы.
- •Экономические постановки задач линейного программирования.
- •Постановка и математическая модель задачи оптимального планирования.
- •Постановка и математическая модель задачи на смеси и соединения
- •Постановка и математическая модель задачи раскроя материалов.
- •Постановка и математическая модель транспортной задачи.
- •Постановка и математическая модель задачи о назначении.
- •Линейная зависимость системы векторов, ранг системы векторов.
- •Разложение вектора по векторам базиса.
- •Метод Жордана-Гаусса, решение систем линейных уравнений.
- •Постановка и математическая модель распределительной (х-задачи).
- •Формы записи задачи линейного программирования (общая, векторная, матричная).
- •Виды решений систем линейных уравнений.
- •Выпуклое множество и его особые точки.
- •Теорема о представлении.
- •Теорема об экстремуме целевой функции.
- •Свойство решений задачи линейного программ-я.
- •Теорема об опорном плане.
- •Геометрическая интерпретация задачи линейного программирования.
- •Графический метод решения задачи линейного программирования с двумя неизвестными
- •Графический метод решения задачи линейного программирования с п неизвестными.
- •Формы задачи линейного программирования. Переход от одной формы к другой.
- •24. Симплексный метод решения задачи линейного программирования:
- •25. Метод искусственного базиса.
- •Несовместность условий в линейном программировании.
- •Двойственность в линейном программировании:
- •Транспортная задача, ее модель.
- •Методы построения первого опорного плана транспортной задачи.
- •Вырожденность в транспортной задаче.
- •Альтернативный оптимум в транспортной задаче.
- •Запреты в транспортной задаче.
- •35 Задача динамического программирования. Функция Беллмана.
- •36. Задачи целочисленного программирования. Метод ветвей и границ. Метод Гомори.
- •37.Задачи нелинейного программирования.
Методы построения первого опорного плана транспортной задачи.
-метод наименьших тарифов (стоимости). Выбирается минимальный тариф, c0 = min(cij);Теорема. Если для некоторого распределения транспортной задачи выполняются условия: а) ui+vj=сij – для занятых клеток; б) ui+vj ≤сij – для свободных клеток, то данное распределение является оптимальным. Величины ui называют потенциалами строк, а величины vj называют по-тенциалами столбцов. Алгоритм: Построение первого опорного плана; Проверка вырожденности плана; Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы; Проверка условия оптимальности; Построение нового опорного плана.
-метод северо-западного угла. Выбирается первый тариф начиная с первого, c0 = c11; При построении исходного распределения с помощью данного метода, из оставшихся клеток выбирается левая верхняя клетка (северо-западная). На первом этапе выбирается клетка (1,1). В эту клетку записывается объём поставки х11= min {А1,В1}. Величины А1 и В1 уменьшаются на данную величину. Ту строку или столбец, где будет получен 0, удаляют из рассмотрения. Затем из оставшихся клеток, рассматривают левую верхнюю клетку и поступают аналогично. Продолжая данный процесс, мы заполним клетку (m,n), причем удалим из рассмотрения и строку и столбец. Если в процессе заполнения клеток придётся вычеркнуть и строку, и столбец, то мы получим вырожденное распределение (количество занятых клеток меньше, чем m+n-1).
31. Метод потенциалов: Теорема. Если для некоторого распределения транспортной задачи выполняются условия: а) ui+vj=сij – для занятых клеток; б) ui+vj ≤сij – для свободных клеток, то данное распределение является оптимальным. Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов
Переход от одного опорного решения к другому: Выбираем клетук с наибольшей положительной оценкой. Для этой клетки строится цикл, все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение.
Вырожденность в транспортной задаче.
Вырожденность – когда не хватает клеток-уравнений для определения потенциалов в плане, когда необходимо для нормальной работы m+n-1 уравнение, а их, к сожалению, m+n-2. Это происходит в процессе заполнения клеток, когда приходится вычеркнуть и строку, и столбец, мы получим вырожденное распределение (количество занятых клеток меньше, чем (m+n-1). Чтобы этого не произошло, из рассмотрения удаляем что–то одно: или строку, или столбец, а оставшийся столбец или строку считают с нулевой потребностью или запасами.