Решение оптимизационной задачи линейного программирования. 2
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
филиал федерального государственного бюджетного
образовательного учреждения
высшего профессионального образования
«Воронежский государственный
архитектурно-строительный университет»
в городе Борисоглебске
Кафедра экономики и управления строительством
Курсовая работа
по дисциплине «Оптимизационные задачи в экономике»
Тема «Решение оптимизационной задачи линейного программирования»
направление «Менеджмент»
Борисоглебск
2012
Содержание
Введение…………………………………………………………
I.Теоретическая часть……………………………………………………………6
1 Постановка
задач и оптимизации……………………………
2 Построение
аналитической модели…………………………
3 Обоснование
и описание вычислительной
3.1 Приведение
задач линейного
3.2 Основная
идея симплекс метода…………………………
II Практическая часть………………………………………………………….22
Заключение……………………………………………………
Список используемой
литературы……………………………………………..
Введение
В настоящее
время оптимизация находит
Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Поиски оптимальных решений привели к созданию специальных
математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
( количество продукции - расход сырья
( количество продукции - качество продукции
Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
При постановке задачи оптимизации необходимо:
1. Наличие объекта оптимизации и цели оптимизации. При этом
формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.
2. Наличие ресурсов оптимизации, под которыми понимают возможность
выбора значений некоторых параметров оптимизируемого объекта.
3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
4. Учет ограничений.
Обычно оптимизируемая величина связана с экономичностью работы
рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.
Критерием оптимальности называется количественная оценка
оптимизируемого качества объекта.
На основании выбранного критерия оптимальности составляется целевая
функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом, задача оптимизации сводится к нахождению экстремума
целевой функции.
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования.
Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.
Итак, линейное программирование возникло после Второй Мировой
Войны и стал быстро развиваться, привлекая внимание математиков,
экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».
Можно сказать, что линейное программирование применимо для
построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств.
Линейное программирование представляет собой наиболее часто
используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
- рационального использования сырья и материалов; задачи оптимизации раскроя;
- оптимизации производственной программы предприятий;
- оптимального размещения и концентрации производства;
- составления оптимального плана перевозок, работы транспорта;
- управления производственными запасами;
- и многие другие, принадлежащие сфере оптимального планирования.
Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.
1. Постановка задач оптимизации.
2.Построение аналитической модели.
Сама по себе постановка задачи оптимизации проста и естественна:
заданы множество и функция , определенная на , требуется найти точки минимума или максимума.
Условимся записывать задачу на минимум в виде:
( 2.1.1 )
где
- целевая функция;
- допустимое множество
- допустимая точка задачи ( 2.1.1 ).
В основном мы будем иметь дело с конечномерными задачами оптимизации, то есть с задачами, в которых допустимое множество лежит в евклидовом пространстве ().
Точка , являющаяся решением задачи ( 2.1.1 ), может быть точкой глобального или локального минимума.
Точка называется
1) точкой глобального минимума функции на множестве или глобальным решением задачи ( 2.1.1 ), если
( 2.1.2 )
2) точкой локального минимума функции на множестве или локальным решением задачи ( 2.1.1 ), если
,такое что для ( 2.1.3 )
где
Если неравенство в ( 2.1.2 ) или в ( 2.1.3 ) выполняется как строгое при то - точка строгого минимума (строгое решение) в глобальном или локальном смысле.
Для отражения того факта, что точка является точкой глобального минимума функции на множестве , обычно используется запись
или эквивалентная ей запись
Множество всех точек
где - минимальное значение функции на множестве .
В этом случае - это просто произвольная точка из множества
По аналогии с ( 2.1.1 ) записывают задачу максимизации функции на множестве , в виде
, ( 2.1.4 )
Заменяя в данных выше определениях слово «минимум» на «максимум» и заменяя знак неравенств в ( 2.1.2 ), ( 2.1.3 ) на противоположный, получаем соответствующие понятия для задачи ( 2.1.4 ).
Решения задач ( 2.1.1 ), ( 2.1.4 ), то есть точки минимума и максимума функции на множестве , называются также точками экстремума, а сами задачи ( 2.1.1 ), ( 2.1.4 ) - экстремальными задачами.
Ясно, что задача ( 2.1.4 ) эквивалентна задаче
, ,
в том смысле,
что множества глобальных и локальных,
строгих и нестрогих решений
этих задач соответственно совпадают.
Это позволяет без труда
При изучении задач оптимизации в первую очередь возникает вопрос о существовании решения. Ответ на этот вопрос дает теорема Вейерштрасса.
Теорема Вейерштрасса.
Пусть - компакт в , - непрерывная функция на множестве . Тогда точка глобального минимума функции на существует (глобальное решение задачи существует).
Напоминание:
Компакт - замкнутое ограниченное множество.
3
Обоснование и описание
3.1
Приведение задач линейного
Задача линейного программирования состоит в оптимизации линейной функции на многогранном множестве , то есть математически она записывается следующим образом:
, ( 6.1.1 )
где
,
- вектор размерности , ,
- матрица размера ранга ,
- вектор размерности , . ( 6.1.2 )
Скалярное произведение называется целевой функцией. Коэффициенты целевой функции - это координаты вектора .
Множество называется множеством ограничений или допустимой областью задачи линейного программирования.
Задача ( 6.1.1 ) - . ( 6.1.2 ) называется задачей линейного программирования в каноническом виде.
Оптимальное значение целевой функции задачи линейного программирования может быть как конечным , так и неограниченным.
Теорема (условия оптимальности для задачи линейного программирования).
Рассмотрим задачу линейного программирования ( 6.1.1 ) - ( 6.1.2 ).
Пусть , - экстремальные (угловые) точки, - экстремальные направления множества .
Для того, чтобы оптимальное значение целевой функции было конечным, необходимо и достаточно, чтобы .
Если это условие выполняется, то среди решений задачи (оптимальных точек) будет хотя бы одна экстремальная точка .
Из этой теоремы следует, что, по меньшей мере, когда допустимая область ограничена, можно решить задачу линейного программирования, вычислив и затем найти минимальное из всех .
То есть это перебор всех точек многогранного множества. Но количество экстремальных точек для реальных задач велико, и способ перебора неприемлем.
Двойственные задачи линейного программирования.
В теории
линейного программирования чрезвычайно
важную роль играет то обстоятельство,
что каждой задаче линейного программирования
соответствует некоторая двойст
Если исходная задача(прямая)
при условии , ,
то двойственная задача представляет задачу на минимум
при условии , ,
то есть в развернутом виде:
прямая:
двойственная:
В экономике переменные двойственной задачи линейного программирования – это «теневые цены» лимитирующих ресурсов прямой задачи линейного программирования. «Теневая цена» ресурса показывает, насколько увеличится значение целевой функции при снижении лимитирующего ресурса на единицу. Увеличение объема лимитирующего ресурса на единицу целесообразно только в том случае, если существует возможность его получения по стоимости, которая ниже, чем «теневая цена» данного ресурса.
Таблица для двойственных задач линейного программирования :
Если к двойственной задаче применить те же преобразования, какие были сделаны для прямой задачи, то вновь получаем исходную задачу линейного программирования (то есть двойственная к двойственной - есть исходная задача).
Основные теоремы линейного программирования.
Теорема 1(теорема существования).
Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы допустимые множества как прямой, так и двойственной задач были не пусты.
Теорема 2(теорема двойственности).
Некоторый допустимый вектор тогда и только тогда является решением задачи линейного программирования, когда существует такой допустимый вектор двойственной задачи, что значения целевых функций обеих задач на этих векторах равны.
Теорема 3(теорема о дополняющей не жесткости).
Для того, чтобы допустимые векторы являлись решениями двойственных задач, необходимо и достаточно, чтобы они удовлетворяли условиям дополняющей не жесткости, то есть:
Геометрическое изображение двойственных задач при m=n=2.
Альтернативные варианты , возникающие при решении задач линейного программирования.
3.2 Основная идея симплекс метода
Симплексный метод - некоторая систематическая процедура решения задачи линейного программирования, состоящая в движении от одной экстремальной точки допустимой области к другой с лучшим(или по крайне мере не худшим) значением целевой функции. Процесс продолжается до тех пор, пока не будет найдена либо оптимальная экстремальная точка, либо экстремальное направление , для которого (в этом случае оптимальное значение целевой функции неограниченно).
Рассмотрим каноническую форму задачи линейного программирования:
Задача линейного программирования, где многогранное множество записано в другом виде:
можно представить в каноническом виде, то есть записать неравенство в виде равенства. Для этого необходимо ввести неотрицательную дополнительную переменную :
Аналогично переменные , на которые не наложено требование не отрицательности переменных, представляются в виде:
Эти и некоторые другие преобразования используются для приведения задачи к каноническому виду.
Предположим,
что множество ограничений
Возьмем некоторую экстремальную (угловую) точку .
В силу теоремы (о характеристике экстремальных точек) эту точку характеризует представление матрицы A в виде ,
где В - матрица m x m полного ранга, называемая базисом, N - матрица m x (n-m) .
По этой же теореме вектор может быть представлен
Переменные, соответствующие столбцам матрицы В, называются базисными и обозначаются . Остальные переменные, соответствующие столбцам матрицы N, называются внебазисными.
Рассмотрим теперь произвольную точку для которой , и представим ее в виде
, тогда равенство можно записать в виде .
Следовательно
( 6.4.1 )
Используя ( 6.4.1 ) получаем
( 6.4.2 )
Если , то в силу не отрицательности справедливо неравенство
и - оптимальная экстремальная точка.
Пусть
В частности пусть для некоторого j компонента
Рассмотрим точку
, где
- (n - m) - мерный единичный вектор
Тогда из ( 6.4.2 ) следует, что
( 6.4.3)
так как
то
при
Положим
и рассмотрим 2 случая:
- Так как , то для при всех
Следовательно, x - допустимая точка тогда и только тогда, когда .
Очевидно, что при это справедливо для всех . Но тогда из ( 6.4.3) следует, что значения целевой функции не ограничены.
- . Пусть определено соотношением
( 6.4.4 )
где
есть i - ая компонента вектора .
В этом случае компоненты вектора определяются следующим образом:
( 6.4.5 )
, остальные компоненты равны нулю.
Положительными могут быть только , то есть не более m компонент.
Легко проверить, что соответствующие им столбцы матрицы A линейно независимы. Поэтому в силу теоремы(о характеристике экстремальных точек) точка x сама является экстремальной. То есть в этом случае говорят, что базисная переменная выводится из базиса, а внебазисная переменная вводится в базис на ее место.
Итак, если задана произвольная экстремальная угловая точка, то можно
- либо установить, что она оптимальна;
- либо найти экстремальное направление, приводящее к неограниченному значению целевой функции;
- либо найти экстремальную точку с лучшим значением целевой функции.
В последнем случае процесс повторяется.
- начальный этап:
найти произвольную экстремальную точку x c базисом B. Если это сделать трудно, то использовать метод искусственных переменных.
2) основной этап:
шаг 1:
Пусть x - экстремальная точка c базисом B.
Вычислить
Если этот вектор , то остановится.
x - оптимальная экстремальная точка.
В противном случае выбрать наибольшую компоненту вектора
Предположим такая компонента - .
Если вектор , то остановится, поскольку в этом случае оптимальное значение целевой функции неограниченно вдоль луча
где - (n - m) - мерный единичный вектор.
Если , то перейти к шагу 2.
шаг 2:
Вычислить номер r в соответствии с ( 6.4.4 ) и построить новую экстремальную точку по формуле ( 6.4.5 ).
Сформировать новый базис, выводя из B столбец и вводя вместо него Повторить шаг 1.
Табличное представление симплекс - метода.
Пусть имеется начальный базис B, соответствующий начальной экстремальной точке. Целевая функция и ограничения задачи линейного программирования могут быть записаны в виде:
строка - целевая функция
строки-ограничения
Эти равенства можно свести в следующую симплекс - таблицу, в которой правая часть(ПЧ) соответствует их правым частям.
ПЧ | |||
1 |
0 | ||
0 |
B |
N |
b |
Строки-ограничения преобразуются умножением на (). К строке целевая функция прибавляются новые строки- ограничения, умноженные на . При этом получается следующая преобразованная таблица:
ПЧ | ||||
1 |
||||
0 |
1 |
Базисные переменные отмечены в таблице слева, а значения базисных переменных записаны в правой части таблицы.
Эта таблица содержит всю информацию, необходимую для завершения первого шага симплекс метода.
Если процесс прекращается, то есть текущая точка является оптимальной.
В противном случае:
при просмотре строки целевой функции можно выбрать внебазисную переменную с положительным значением
где
- вектор
- матрица
- вектор
- скаляр
Если - то процесс прекращается - значение целевой функции неограниченно.
Если , то
так как записаны под ПЧ и соответственно, то следуя ( 6.4.4 ) легко вычислить .
Базисная переменная , соответствующая минимальному отношению в ( 6.4.4 ), выводится из базиса, а вводится в базис.
Далее проводим ведущее преобразование:
Строка, соответствующая (выводимая переменная из базиса) - ведущая строка.
Столбец, соответствующий (вводимая переменная в базис) - ведущий столбец.
- Разделить ведущую строку(соответствующую ) на ведущий элемент ;
- Умножить новую r - ую строку на и результат вычесть из i - ой строки ограничений для всех
- Умножить новую r - ую строку на и результат вычесть из строки целевой функции.
Пример:
Графически:
Оптимальной является точка . Значение функции
- приводим задачу линейного программирования к канонической форме:
Возьмем в качестве В матрицу
Так как ,
то найдена экстремальная точка:
ПЧ | ||||||
1 |
-1 |
3 |
0 |
0 |
0 | |
0 |
-1 |
2 |
1 |
0 |
6 | |
0 |
1 |
1 |
0 |
1 |
5 |
- выводится из базиса
- вводится в базис
Новый базис
ПЧ | ||||||
1 |
0 |
0 |
-9 | |||
0 |
1 |
0 |
3 | |||
0 |
0 |
1 |
2 |
Теперь:
- выводится из базиса
- вводится в базис.
Новый базис
ПЧ | ||||||
1 |
0 |
0 |
||||
0 |
0 |
1 |
||||
0 |
1 |
0 |
Так как , то получено оптимальное решение.
Выбор начальной экстремальной точки.
Для использования симплекс - метода необходимо задать некоторую начальную экстремальную точку.