Автор работы: Лена Шугалеева, 25 Сентября 2010 в 19:08, курсовая работа
Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) bi , где gi - функция, описывающая ограничения, - один из следующих знаков , , , а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).
Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.
Задачу линейного программирования можно сформулировать так . Найти max
при условии : a11 x1 + a12 x2 + . . . + a1n xn b1 ;
a21 x1 + a22 x2 + . . . + a2n xn b2 ;
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
am1 x1 + am2 x2 + . . . + amn xn bm ;
x1 0, x2 0, . . . , xn 0 .
Эти ограничения называются условиями неотрицательности. Если все ограни-чения заданы в виде строгих равенств, то данная форма называется канонической.
- 7 -
В матричной форме задачу линейного программирования записывают следующим образом. Найти
max cT x
при условии
A x b ;
x 0 ,
где А - матрица ограничений размером ( mn), b(m1) - вектор-столбец свобод-ных членов, x(n 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции.
Решение х0 называется оптимальным, если для него выполняется условие сТ х0 сТ х , для всех х R(x).
Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
Для решения задач данного типа применяются методы:
1) графический;
2) табличный ( прямой, простой ) симплекс - метод;
3) метод искусственного базиса;
4) модифицированный симплекс - метод;
5) двойственный симплекс - метод.
1.2 Табличный симплекс - метод
Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.
Алгоритм решения сводится к следующему :
Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.
Если в исходной системе ограничений присутствовали знаки “ равно ”
- 8 -
или “ больше либо равно ”, то в указанные ограничения добавляются
искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.
Формируется симплекс-таблица.
Рассчитываются симплекс-разности.
Принемается решение об окончании либо продолжении счёта.
При необходимости выполняются итерации.
На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.
- 15 -
Так как все симплекс-разности положительны, то оптимальное решение найдено :
X = ( 7/2 , 3/4 , 11/4 , 0 , 0 ) ( единиц )
max F =
9 1/4 ( рублей )
- 16 -
4.
АНАЛИЗ МОДЕЛИ
НА ЧУВСТВИТЕЛЬНОСТЬ
4.1 Построение двойственной задачи и её
численное решение
Проведение анализа на чувствительность связано с теорией двойственности, поэтому в курсовой работе необходимо построить двойственную задачу и найти её численное решение.
Для рассматриваемой модели двойственная задача имеет вид :
min T( y ) = min ( 10y1 + 12y2 + 10y3 ) при условиях
Оптимальное решение двойственной задачи получается при решении прямой задачи из последней симплекс-таблицы. В результате получаем оптимальное решение двойственной задачи :
Yопт = ( 0, 1/4, 5/8, 0, 0 ), для которого Т(yопт) = 9 1/4.
Оптимальное
значение целевой функции в двойственной
задачи совпадает с оптимумом целевой
функции прямой задачи, в чём не трудно
убедиться.
4.2 Определение статуса ресурсов
Ресурсы
относятся к дефицитным, если оптимальный
план предусматривает их полное использование,
при частичном использовании
ресурсов, они считаются не дефицитными.
Статус ресурсов для любой модели
линейного программирования можно
установить непосредственно из оптимальной
симплекс-таблицы исходной по значению
дополнительных переменных. Положительное
значение до -
-
17 -
полнительной переменной указывает на неполное использование соответствующего ресурса, т.е. на его недефицитность, нулевое значение дополнительной переменной указывает на дефицитность ресурса.
Для
данного примера дополнительные
переменные х4 и х5 равны
нулю, следовательно, оборудование второго
и третьего типов являются “дефицитными”,
а первого типа - “недефицитным” ( х3
= 2,75 ). Такой же вывод можно сделать из
решения двойственной задачи.
4.3 Определение значимости
Значимость
ресурса характеризуется
В
данном случае Yопт = ( 0, 1/4, 5/8, 0, 0 ).
Таким образом, из двух “дефицитных”
ресурсов оборудование второго типа имеет
большую значимость и увеличении интервала
работы на этом оборудовании более выгодно
с точки зрения влияния на значение целевой
функции.
4.4 Определение допустимого
Изменение отведённого
Оборудование
второго типа, которое используется
для изготовления изделий, является “дефицитным
и имеет большую значимость. Определим
диапазон допустимых изменений интервала
работы на этом оборудовании. Оптимальная
-
18 -
симплекс-таблица задачи имеет вид :
| C | 2 | 3 | 0 | 0 | 0 | ||
| Б | Cб | A0 | A1 | A2 | A3 | A4 | A5 |
| A2 | 3 | 3/4 | 0 | 1 | 0 | -1/4 | 3/8 |
| A3 | 0 | 11/4 | 0 | 0 | 1 | 3/4 | -13/8 |
| A1 | 2 | 7/2 | 1 | 0 | 0 | 1/2 | -1/4 |
| d | 9 1/4 | 0 | 0 | 0 | 1/4 | 5/8 |
Так как начальными базисными переменными являлись x1, x2, x3 в оптимальной симплексной таблице в соответствующих столбцах расположена матрица А-1 Изменим время работы на оборудование второго типа на величину D2, тогда время работы будет 12 + D2 .
Найдём
базисное решение, соответствующее
изменённому времени работы на оборудовании
второго типа :
0.75 - D2 / 4 ³ 0 , D2 = 3;
2.75 + 3D2 / 4 ³ 0 , D2 = -3.66;
3.5 + D2 / 2 ³ 0 , D2 = -7.
Отсюда видно, что -3.66 £ D2 £ 3 , т.е. 8.34 £ b2 £ 15 .
Таким
образом первоначальный интервал работы
на оборудовании второго типа может
быть увеличен до 15 часов или уменьшен
до 8.34 часа без нарушения допустимого
решения. Уменьшение времени влечёт за
собой уменьшение единиц вырабатываемой
продукции, поэтому является не целесообразным.
- 19 -
4.5 Исследование зависимости
изменений запасов ресурсов
Изменение свободного члена ограничения исходной задачи на величину D2 вызывает изменение целевой функции на DF = D i × y j .Если приращение времени работы берётся из интервала допустимых изменений, значений двойственных оценок остаются неизменными. Таким образом, изменение целевой функции будет линейно зависеть от изменения времени работы.
В данном примере DF = D i × 12 = 12 × D i . Ищется зависимость значений целевой функции от изменения времени работы на оборудовании второго типа. Для этого изменяется время работы начиная от 0 часов с шагом h = 0.5 до 3 часов. Результаты измерений приведены в таблице 1.
Таблица 1
| D2, часов | 0 | 0.5 | 1 | 1.5 | 2 | 2.5 | 3 |
| b2, часов | 12 | 12.5 | 13 | 13.5 | 14 | 14.5 | 15 |
| DF, руб. | 0 | 6.25 | 13 | 20.25 | 28 | 36.25 | 45 |
| F, руб. | 9.25 | - | - | - | - | - |
Т.к. зависимость F( b2 ) - линейная, то достаточно подсчитать значение функции в двух крайних точках интервала.
Cледовательно,
с увеличением времени работы
на оборудовании второго типа
на 2 часа увеличивается и объём
изделий на общей стоимостью 28
рублей.
- 20 -
5. ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ПОЛУЧЕННЫХ
РЕЗУЛЬТАТОВ
Графический метод применим только для двух и менее переменных х, что подходит к данному заданию. Линии, соответствующие ограничения, строятся на осях Ох. Заштрихованная область - область допустимых стратегий.
x1 + 5x2 £ 10 ;
3x1 + 2x2 £ 12 ;
2x1 + 4x2 £ 10 .
x1 ³ 0 ; x2 ³ 0 .
1). x1 + 5x2 £ 10 ;
x1 = 0, x2 = 2 ;
x1 = 10, x2 = 0 .
2). 3x1 + 2x2 £ 12 ;
x1 = 0, x2 = 6 ;
x1 = 4, x2 = 0 .
3). 2x1 + 4x2 £ 10 ;
x1 = 0, x2 = 2.5 ;
x1 = 5, x2 = 0 .
4). Найдём экстремум функции :
F = 2x1 + 3x2 ,
Графически
область допустимых решений показана
на рисунке 1.
-
21 -
Рисунок
1 - Область допустимых решений данной
системы.
- 22 -
6. ВЫВОДЫ И РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ
ИСПОЛЬЗОВАНИЮ
Составление математической модели и решение систем линейных неравенств часто имеет место в реальной жизни. Примеры таких задач :
Пример 1. Рассматривается работа промышленного предприятия под углом зрения его рентабельности, причём приводится ряд мер с целью повышения этой рентабельности. Показатель эффективности - прибыль ( или средняя прибыль ), приносимая предприятием за хозяйственный год.
Пример 2. Группа истребителей поднимается в воздух для перехвата одиночного самолёта противника. Цель операции - сбить самолёт. Показатель эффективности - вероятность поражения цели.