- •Математические методы теории оптимизации. Понятие экстремальных задач, примеры. Основные понятия лп.
- •Историческая справка.
- •Задача планирования производства.
- •Задача о рационе.
- •Транспортная задача.
- •Раздел 1. Линейное программирование.
- •Определение канонической формы задач.
- •Основные свойства решения задач лп
- •Элементы выпуклого анализа.
- •Множество решений задачи линейного программирования (если оно не пусто) является выпуклым многогранником.
- •Любая точка многогранника решений является линейно - выпуклой комбинацией его угловых точек. Опорное и базисное решение.
- •Алгебраическая характеристика угловой точки.
- •Симплексный метод.
- •Задача № 1.
- •Правило определения вектора вводимого в базис.
- •Метод искусственного базиса (м-метод).
- •Расширенная задача.
- •Исходная симплекс-таблица расширенной задачи.
- •Теория двойственности в линейном программировании.
- •Экономическая интерпретация
- •Виды моделей двойственных задач.
- •Соответствие между прямой и двойственной задачами.
- •Нахождение решения двойственной задачи по симплекс-таблице оптимального решения прямой задачи.
- •Экономическая интерпретация двойственности.
- •Экономическая интерпретация переменных двойственных задач.
- •Раздел II. Специальные задачи лп Целочисленное программирование.
- •Задачи целочисленного программирования.
- •Пример: «Задача о рюкзаке (задача загрузки корабля)»
- •Пример: «Задача о распределение инвестиций»
- •Первый алгоритм Гомори (аддитивный)
- •Алгоритм Гомори состоит из двух шагов:
- •Метод ветвей и границ.
- •Специальные виды целочисленных задач. Транспортная задача
- •Методы решения транспортной задачи
- •Вторая транспортная теорема
- •Метод потенциалов (Канторович)
- •Алгоритм решения
- •Задача о назначениях. Венгерский алгоритм.
- •А лгоритм решения:
Нахождение решения двойственной задачи по симплекс-таблице оптимального решения прямой задачи.
Предположим, что найден оптимальный план X* прямой задачи, который (не ограничивая общности) определяется системой базисных векторов Ai1,…Aim. Через С*Б – обозначим вектор, состоящий из коэффициентов целевой функции при базисных переменных оптимального решения.
Через P-1 обозначим матрицу, обратную матрице P, составленную из компонент векторов Ai1,…Aim оптимального базиса.
Теорема 6.4:
Если прямая задача имеет оптимальный план X*=(X ,…X ), то оптимальный план двойственной задачи Y*=С*Б P-1.
Практически: решение двойственной задачи находится в симплекс-таблице оптимального решения прямой на пересечении индексной строки и векторов исходного базиса прямой задачи.
Экономическая интерпретация двойственности.
Рассмотрим следующую ситуацию: имеется m видов ресурсов в объемах B1,…Bm. И на основании этих ресурсов предполагается выпускать продукцию n различными способами. При этом за единицу времени применения j-ого способа расходуется aij единиц i-того вида ресурса. И выпускаемая при этом продукция имеет ценность Cj – единиц. Как оценить имеющиеся ресурсы?
Пусть вектор x=(x1,…xn), компоненты которого есть время использования j- ого способа производства (xj 0). Тогда aijxj B.
Через Z= cjxj обозначим ценность продукции, выпускаемой при использовании плана x. Если yi – оценка единицы i-того вида ресурсов, то aijyi – оценка всех ресурсов, расходуемых в единицу времени при использовании j-огоспособа производства. Эта величина не может быть меньше ценности выпускаемой при тех же условиях продукции. Величина W(Y)= biyi – оценка всех используемых ресурсов при выбранном векторе оценок Y =(y1….. yn)
Для любого X и Y ценность выпускаемой продукции не превосходит суммарной оценке имеющихся ресурсов: Z(X) W(Y) величина (X,Y)=W(Y)-Z(X) характеризует производственные потери в зависимости от плана X и выбранных оценок ресурсов Y.
X и Y надо выбирать так, чтобы величина потерь была наименьшей, а для этого достаточно подобрать план так, чтобы Z(X) было как можно больше, а W(Y) было как можно меньше, поэтому и возникает пара двойственных симметричных задач.
Из первой теоремы двойственности следует, что оптимальному вектору решений задачи планирования и оптимальному вектору оценок ресурсов производственные потери равны 0.
Из второй теоремы двойственности следует следующее соотношение:
Если y >0, то aijx =Bi (*)
Если aijx <Bi, то y =0
Если x >0, то aijy =cj (**)
Если aijy ≥cj x =0
Условие (*) интерпретируется следующим образом:
Если в оптимальном плане оценка i-того вида ресурса положительна, то этот ресурс используется полностью в полученном оптимальном плане прямой задачи.
Если ресурс используется не полностью в оптимальном плане, то его оценка равна 0. Оценка превращается в цену единицы ресурса лишь при условии, когда ресурс становится дефицитным в полученном оптимальном плане.
Из условия (**) следует:
Если производство j-ого вида продукции включено в оптимальный план, то он в оптимальных оценках не убыточен (цена его реализации совпадает с затратной оценкой). Затратной оценкой называется оценка всех ресурсов, затраченных на производство единицы j-вида продукции.
Если j-вид продукции убыточен, то в оптимальном плане его производство не предусмотрено.