Автор работы: Пользователь скрыл имя, 12 Марта 2012 в 17:20, курсовая работа
В 1938-1939 гг. ленинградский математик (впоследствии академик, лауреат Ленинской, Государственных и Нобелевской премий) Л. В. Канторович в результате анализа ряда проблем организации и планирования производства сформулировал новый класс условно-экстремальных задач и предложил методы их решения. Так было положено начало новой отрасли прикладной математики линейному программированию. В более поздних работах Л. В. Канторович расширил область применения линейного программирования в социалистической экономике, сформулировав задачи отраслевого и народнохозяйственного оптимального планирования
Введение
37
Теоритическая часть
Оптимизационные модели
38
56
История развития экономико – математического планирования
38
Классификация математических моделей
38
Оптимизационные экономико – математические модели
40
Понятие оптимизационных задач и оптимизационных моделей
42
Экономические основы оптимизации
47
Классификация задач оптимального планирования
48
Симплекс – метод
48
Идея симплекс – метода
50
Построение начального опорного план
51
Геометрическая интерпритация симплексного метода
51
Определение первоначального допустимого базисного решения
53
Симплексные таблицы
55
Метод искусственного базиса
55
Каноническая форма
57
Алгоритм метода искусственного базиса
2.6.3. Правила преобразования базиса симплексной таблицы
Практическая часть
Симплексным методом с искусственным базисом решить каноническую задачу линейного программирования. Выполнить проверку оптимальности полученного решения, используя теорию двойственности. Найти оптимальное решение двойственной задачи.
Заключение
Список использованных источников
am,1x1+am,2x2+...am,nxn+xn+m=b
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, xn+m , к каждому i-му условию-равенству добавляем искусственную переменную Ri.
Шаг 1. Составляем симплексную таблицу, соответствующую исходной задаче:
x1 |
x2 |
... |
xn-1 |
xn |
b | |
F |
-a0,1 |
-a0,2 |
... |
-a0,n-1 |
-a0,n |
-b0 |
|
xn+1 |
a1,1 |
a1,2 |
... |
a1,n-1 |
a1,n |
b1 |
|
xn+2 |
a2,1 |
a2,2 |
... |
a2,n-1 |
a2,n |
b2 |
|
Ri |
ai,1 |
ai,2 |
... |
ai,n-1 |
ai,n |
bi |
|
... |
... |
... |
... |
... |
... |
... |
xn+m |
am,1 |
am,2 |
... |
am,n-1 |
am,n |
bm |
|
M |
-∑ai,1 |
-∑ai,2 |
... |
-∑ai,n-1 |
-∑ai,n |
-∑bi |
Шаг 2. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.
Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 3. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строках M и F(не беря в расчет элемент b0- текущее значение целевой функции и элемент -∑bi) нет отрицательных, то найдено оптимальное решение.
2.1. Положительность строки M
Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑bi)
l - столбец в котором он
bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0
k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.
Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2.
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2.
2.2. Положительность строки F
Проверяем на положительность элементы строки F. Если имеются отрицательные элементы (не считая b0), выбираем среди отрицательных элементов строки F максимальный по модулю.
-a0,l=min{-a0,i }
l - столбец в котором он
bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0
k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.
Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
2.6.3. Правила преобразований симплексной таблицы
При составлении новой симплекс-
Информация о работе Оптимизационные модели. Метод искусственного базиса (М-метод)