Реферат Решение задач линейного программирования 3

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Курсовая работа Дипломная работа Контрольная работа Реферат Отчет по практике Эссе Доклад Решение задач Научно-исследовательская работа Монография Аспирантский реферат Магистерская работа Научная статья Публикация статьи в ВАК Публикация статьи в Scopus Дипломная работа MBA Бизнес-план Тест/экзамен online Чертеж Рецензия

Принимаю Политику конфиденциальности

Продолжить

Скидка 25% при заказе до 26.11.2024

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«БРЕСТСКИЙ ГОСУДАОСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра информатики и прикладной математики
КУРСОВАЯ РАБОТА

на тему

«РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ»

по дисциплине «Системный анализ и исследование операций»
                                                                                                    Выполнил студент
                                                                                                    Допущен к защите
                                                                                                    Результаты защиты
БРЕСТ 2009


СОДЕРЖАНИЕ
Введение………………………………………………………………………………

Постановка задачи оптимизации……………………………………….

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ………………………………...

Обоснование выбора метода решения задачи……………………

Решение задачи оптимизации…………………………………………….

АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ И УСТОЙЧИВОСТЬ………

              Предварительный анализ оптимального решения………………...

              Исследование чувствительности целевой функции………………..

              Исследование устойчивости оптимального базисного плана……..

ПОИСК ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ………………..

ЗАКЛЮЧЕНИЕ………………………………………………………………………….

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ…………………………………….



                                         

 Введение
Исследование операций изучает хорошо структурированные задачи. Хорошо структурированная задача – задача, для которой существует математическая модель с одним критерием качества. Математическая модель – отражение интересующих нас свойств объектов или явлений с помощью математических символов.

Цель, которую преследуют в процессе исследования операций (ИО), заключается в том, чтобы выявить наилучший (оптимальный) способ действия при решении той или иной задачи организационного управления в условиях, когда имеют место ограничения технико-экономического или какого-либо другого характера. Когда используют термин исследование операций, то почти всегда имеют в виду применение математических методов для моделирования систем и анализа их характеристик. Действительно, математические модели и методы занимают в исследовании операций центральное место.

Исследование операций можно рассматривать и как науку, и как искусство. Правомерность утверждения о научности вытекает из того обстоятельства, что при решении возникающих проблем эффективно используются математические модели и методы. Исследование операций можно рассматривать и как искусство, поскольку успешное выполнение всех этапов исследования во многом определяется творческими способностями и интуицией исследователей. Поэтому при сборе информации, необходимой для построения математической модели, верификации модели и использовании получаемых с помощью модели результатов успех, несомненно, зависит от способности исследователей устанавливать рабочие контакты как с источниками необходимой информации, так и с лицами, ответственными за реализацию принимаемых решений.

Математическая  модель – отображение оригинала в виде математических объектов, переменных, функций, уравнений и неравенств.

В простейшем случае математическая модель содержит три объекта:

1.       совокупность неизвестных величин x
i
,
i
=1..
n, значения которых необходимо найти. В совокупности эти значения образуют множество решений.

2.       множество допустимых решений которые могут принимать x
i
,
i
=1..
n. В хорошо формализованных задачах это множество может быть описано с помощью системы неравенств  g
j
(
x
1
, x
2
, .. ,
x
m
)<=0,
j
=1..
m
.

3.       оценка качества допустимого решения. В простейшем случае оценка качества осуществляется с помощью специальной функции f(x1,x2,…,xn), которую называют целевой функцией.

В зависимости от ситуации необходимо найти такое допустимое решение, при котором целевая функция принимает максимальное или минимальное значение:

f
(
x
1,
x
2,…,
xn
)
à

extr
(
max
,
min
)

g_i
(
x
1,
x
2,…,
xn
)<= 0,
i
=1..
n
, где  g – ограничение целевой функции.

Такая задача в которой множество решений может быть описано с помощью системы функциональных равенств и неравенств, называется задачей математического программирования. . Для решения задач этого типа разработан специальный раздел математики, который называется математическим программированием.

Но не всегда удается сформулировать ограничение задачи в виде совокупности равенств или неравенств. Не всегда удается сформулировать цель в виде одной целевой функции, поэтому в общем случае математическая модель задачи может выглядеть более абстрактно:

Имеется множество допустимых решений X
.Имеется совокупность критериев K
{
K
₁
,
K
₂
,...,
K_n
} с помощью которых производится оценка качества решений X. Требуется найти такое решение x
Î
X, которое является наилучшим с точки зрения критериев K
₁
,
K
₂
,...,
K_n. Такая задача и будет называться задачей исследования операций.

Классификация задач исследования операций.

1.    
Постановка задачи оптимизации

                                                                            

3. Обоснование выбора метода решения задачи

                                                                   (3.1)

                                    

                                                  (3.3)

, .

                                                              (3.5)

                                                              (3.6)

1.   Симплекс-метод в табличной форме.

Предположим, что задача линейного программирования в канонической форме приведена к симплексной форме (3.6). Перенесем коэффициенты целевой функции вектора свободных членов  и матрицы

 в специальную симплексную таблицу:

б\н	B		…		…		…
L		r	…	r	…	r	…	r
			…		…		…
…	…	…	…	…	…	…	…
			…		…		…
…	…	…	…	…	…	…	…
			…		…		…
…	…	…	…	…	…	…	…

, то базисный план, соответствующий симплексной таблице является оптимальным и решение ЗПП окончено.

                                                      (3.7)

Очевидно, что соотношение (7) может нарушаться только в том случае, если , поэтому для каждой базисной переменной :

, то соответствующая базисная переменная ни при каком значении  не обращается в ноль.

Максимально допустимый шаг определим как минимум из чисел .

Это означает, что шаг  может быть бесконечно большим. Соответственно значение целевой функции может неограниченно возрастать, если задача на максимум, или неограниченно убывать, если задача на минимум. С экономической точки зрения такая ситуация свидетельствует о несоответствии математической модели реальной экономической модели (неучтены или неправильно учтены ограничения задачи). Решение ЗПП при этом считается законченным.

 (конечное число)

 называется ведущей или разрешающей переменной.

Как уже отмечалось в пункте 1,  должна выводиться из базиса, на ее место вводится переменная  — небазисная.

б\н	b		…		…
L			…	R	…	r
			…		…
…	…	…	…	…	…
			…		…
…	…	…	…	…	…

                                                      (
3.9
)

                                            (

                                                        (

,

4)

,

,

5. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ И УСТОЙЧИВОСТЬ
5.1. Предварительный анализ оптимального решения
Первые три ограничения являются количественными, т.к. исходят из обязательного заданного объёма перевозок.

Остальные три ограничения являются ресурсными, т.к. исходят из общего времени эксплуатации судов. Очевидно, что при увеличении времени эксплуатации максимальная загрузка судов будет увеличиваться
5.2. Исследование чувствительности целевой функции

Для исследования чувствительности целевой функции к изменениям правых частей основных ограничений необходимо найти оптимальный двойственный план:

                                                                                                (5.1)

и исследовать его компоненты. Согласно полученному решению базисными переменными являются х₃, х₄, х₅ ,х₆,х₈,х₁₀.
                
Вычислим обратную матрицу:


Найдём оптимальный двойственный план:


Дадим экономическую оценку полученным результатам:

1) Увеличение заданного объёма перевозок на 1 линии к увеличению суммарной   максимальной загрузки судов не приведёт

2) Увеличение заданного объёма перевозок на 2 линии к увеличению суммарной   максимальной загрузки судов не приведёт

3) Увеличение заданного объёма перевозок на 3 линии на 1 единицу приведёт к увеличению суммарной   максимальной загрузки судов на 1

4) Увеличение общего времени эксплуатации судов на 1 линии на 1 сутки приведёт к увеличению максимальной загрузки судов на 14 млн.тнно-миль.

5) Увеличение общего времени эксплуатации судов на 2 линии на 1 сутки приведёт к увеличению максимальной загрузки судов на 15 млн.тнно-миль.

6) Увеличение общего времени эксплуатации судов на 3 линии на 1 сутки приведёт к увеличению максимальной загрузки судов на 12 млн.тнно-миль.
5.3. Исследование устойчивости оптимального базисного плана

Определим интервал устойчивости

,                                                                                        (5.2)

где - максимально возможное уменьшение, а  - увеличение правой части i-го ограничения.

Найдём интервал устойчивости для первого ограничения:







Таким образом, интервал устойчивости для b1 составляет:


Найдём интервал устойчивости для второго ограничения:






Таким образом, интервал устойчивости для b2 составляет:


Найдём интервал устойчивости для третьего ограничения:






Таким образом, интервал устойчивости для b3 составляет:


Найдём интервал устойчивости для четвёртого ограничения:







Таким образом, интервал устойчивости для b4 составляет:


Найдём интервал устойчивости для пятого ограничения:







Таким образом, интервал устойчивости для b5 составляет:


Найдём интервал устойчивости для шестого ограничения:







Таким образом, интервал устойчивости для b6 составляет:


6. ПОИСК ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ
Для поиска оптимального целочисленного решения воспользуемся методом ветвей и границ. Для этого нецелочисленную компоненту оптимального решения x3=257.692. Исходя из этого решаем 2 задачи:

1)     x3≤[257.692]=257

2)     x3≥[257.692]+1=258

Решив симплекс-методом задачи с дополнительными ограничениями (1) и (2), получим одно  решения:
       L(x^2*)=11792.308
При ограничении x3≥258 решения не существует.
x^2*  не является целочисленным поэтому процесс решения продолжается дальше. Это решение содержит одну нецелочисленную компоненту х5.
Исходя из этого решаем 2 задачи:

1) x4≤[ 46.154]=46

2)     x4≥[46.154]+1=47
Решив симплекс-методом задачи с дополнительными ограничениями (1) и (2), получим 2 решения:
       L(x^3*)=11792
       L(x^4*)= 11791
Найдено оптимальное целочисленное решение – это решение задачи 3.

Поиск решения можно изобразить графически:
рисунок
Значения основных переменных задачи х₁ , х₂  ,х₃ , х₄,  х_5, х_6, х_7, х_8, х_9, обозначают, что:

-суда 1  типа должны  работать 299 дней на 2 линии и 1 день на 3 линии

-суда 2 типа должны работать 47 дней  на 2 линии и 253 дня на 3   линии

-суда 3 типа должны работать 250 дней на 1 линии и 50 дней на второй линии

При этом максимальная загрузка суден составит 11792 млн. тонно-миль
ЗАКЛЮЧЕНИЕ
В процессе работы над курсовой работой была успешно решена задача по оптимальному распределению судов 3 типов по различным линиям с максимальной загрузкой судов. С помощью симплекс-метода был найден оптимальный базисный план задачи, проведёно  исследование его целевой функции на чувствительность и определены интервалы устойчивости, а так же было найдено оптимальное целочисленное решение.




СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1.     Ракецкий В.М. Методические указания и задания к курсовой работе “Решение задач линейного программирования” по дисциплине “Системный анализ и исследование операций”

Брест: БГТУ 2007

2.     Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.-319с.

3.     Альсевич В.В., Габасов Р., Глушенков В.С. Оптимизация линейных экономических моделей: Статистические задачи. – Мн.: БГУ, 2000. -210с.

4.     Балашевич В.А. Основы математического программирования. – Мн.: Вышэйшая школа, 1985.-173с.

5.     Банди Б. Основы линейного программирования. – М.: Радио и связь, 1989. – 176 с.