|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Линейное программированиеСтр 1 из 4Следующая ⇒
Содержание
Введение ..3 1. Линейное программирование. ....4 1.1. Построение математической модели ЗЛП.. ....4 1.2. Решение ЗЛП графическим методом. ....5 1.3. Решение ЗЛП алгебраическим методом. ....6 1.4. Решение ЗЛП симплекс – методом. ....8 1.5. Решение ЗЛП методом искусственного базиса. ....10 2. Решение ЗЦЛП методом Гомори. ....13 3. Булевское программирование. Метод Баллаша. ....18 4. Поиск глобального экстремума функции…... ....20 4.1. Метод Хука – Дживса. ....20 4.2. Метод градиентного спуска с поятоянным шагом. ....26 5. Одномерная минимизация…. ....27 6. Дополнительное задание. ....32 Заключение. ....39 Список используемой литературы…. ....40 Введение В последние годы все большее значение приобретает математический подход к задачам планирования. Первые работы в этом направлении были сделаны в России ещё в 1937 году. Основной задачей математического планирования в то время была “Оптимизация перевозки угля к узлам реализации за минимальную цену”. Первым её рассматривал русский учёный Л.В. Контарович, авторство которого получило мировое признание. C помощью методов прикладной математики (в частности линейного программирования) решаются такие проблемы, как оптимизация транспортных перевозок, задача о наилучшем использовании сырья, наилучшем плане работы вычислительного комплекса, и многие другие задачи. Решение этих задач позволит значительно снизить экономические затраты на реализацию и эксплуатацию соответствующих проектов. Таким образом, задачи прикладной математики имеют самое обширное применение в жизни. В данной курсовой работе необходимо решить ряд вышеописанных задач, используя методы линейного программирования и безусловной оптимизации. Так же в дополнительном задании для решения задачи используется программа Excel.
Линейное программирование Решение методом искусственного базиса Ограничения – неравенства Ограничения – равенства
-3x1 - 5x2 + 25 -2x1 + 2x2 + 6 x1 + 2x2 – 3 xi
F = - 2x1 + x2 à min ʄ = - 2x1 – 3x2 + x5 + x6 + 5 Свободные х1, х2 Преобразуем систему для решения симплекс – методом
x3 = 25 - (3x1 + 5x2 ) x4 = 6 - ( 2x1 - 2x2 ) ξ1 = 3 - ( x1 + 2x2 - x5) ξ2 = 2 - (x1 + x2 - x6 )
F=0 – ( 2x1 – x2) ʄ = 5 – ( 2x1 + 3x2 – x5 – x6)
На данном этапе все свободные члены равны дробным числам, следовательно данный способ не может быть использован для решения данной задачи.
Вывод: задача линейного программирования решена графическим, алгебраическим методом, симплекс методом. Во всех случаях получены одинаковые решения, что говорит о корректности решения.
Решить ЗЦЛП 3.1Решение ЗЦЛП методом Гомори:
F = x1 + 2x2à max
5x1 + 7x2 ≤ 21 -x1 + 3x2 ≤ 8 x1,x2 ≥ 0 x1, x2 –целые
Приведём к канонической форме
-F = - x1 - 2x2 à min
x1 - 3x2 ≥ - 8
Решим с помощью симплекс – метода
x1 – 3x2 + 8 = x4
x4 = 8 – ( -x1 + 3x2 )
-F = 0 – ( x1 + 2x2 ) àmin
λ = 1/3
λ = 3/22
F опт = 129/22
XT ={ 7/22, 61/22 , 0 , 0 }
β1 = 7/22 – 0 = 7/22 α13 = 3/22 – 0 =3/22 α14 = 15/22 – 0 = 15/22
u1 = -7/22 – ( - 3/22 x3 – 15/22 x4 )
λ = 1/5
Fопт = 29/5
XT ={ 7/15, 8/3 , 0 , 7/15 }
β2 = 8/3 – 2 = 2/3 α2u1 = 1/3 – 0 = 1/3 α23 = 0
u2 = -2/3 – ( - 1/3 u1 – 0 x3 )
λ = -3
Fопт = 27/5
XT ={ 7/5, 2 , 0 , 17/5 }
β1 = 7/5 – 1 = 2/5 α21u2 = 3/5 – 0 = 3/5 α13 = 1/5
u2 = -2/5 – ( - 3/5 u2 – 1/5 x3 )
λ = -5
F опт = 5
XT ={ 1, 2 , 2 , 3} Задача 1
F = x1 + 2x2 à min
-x1 + 3x2 ≤ 8 x2 ≤ 2 x1 ≥ 2 x1,x2 ≥ 0
Эта задача решения не имеет.
Задача 2
F = x1 + 2x2 à min
-x1 + 3x2 ≤ 8 x2 ≤ 2 x1 ≤ 1 x1,x2 ≥ 0
x4 = 8 – ( -x1 + 3x2 ) x5 = 2 – (x2 ) x6 = 1 – ( x1 )
λ = 1
F опт = 5 XT ={ 1, 2 , 2 , 3 , 0 , 0}
Дерево ветвления задачи:
F =5 4.2Булевское программирование. Метод Баллаша Задание:
Решение задач с булевыми переменными можно производить методом ветвей и границ, как с обычными целочисленными переменными, для которых заданы граничные условия Суть этого метода сводится к следующему: 1) расположить переменные по возрастанию коэффициентов при них в целевой функции; 2) принять некоторый набор значений X, удовлетворяющий всем ограничениям; 3) значение целевой функции при удовлетворении п. 2 принять в качестве дополнительного фильтрующего ограничения (фильтра); 4) методом перебора X определить значение фильтрующего ограничения и проверить удовлетворение его заданным ограничениям; 5) если при некотором наборе X значение фильтрующего ограничения окажется для целевой функции лучшим, следует от первоначального набора перейти к новому и продолжить процедуру.
Составим математическую модель данной ЗЛП с булевскими переменными 1: 4x1 + 9x2 + 7x3+ 5x4+6x5 ≤ 30 2: 6x1 + 7x2 + 9x3 + 5x4 + 4x5 ≤ 30 3: 3x1+ 8x2 + 9x3 + 6x4 + 6x5 ≤ 30 F = 10x1 + 15x2 + 10x3 + 25x4 + 20x5 à max
Примем значение целевой функции на наборе 00000 за фильтрующее.
Фильтрующее ограничение:
Максимальное значение 70 функция достигает на наборе 01111. С помошью фильтра Баллаша колличество вычислений было сокращено на 39%. Заключение В ходе курсовой работы были углублены теоретические знания по дисциплине, а также приобретены и закреплены практические навыки решения задач линейного и оценке эффективности работы применяемых алгоритмов. В ходе курсовой работы были изучены задачи линейного программирования, целочисленного линейного программирования и различные алгоритмы их решения. Результаты, полученные различными методами, совпадают, что говорит о корректности решения. Так же изучены методы безусловной оптимизации и поиска глобального экстремума функция. Как и в предыдущем случае, результаты, полученные различными методами, совпадают, что говорит о корректности решения. Список использованной литературы 1. Методические указания для изучения дисциплины «Прикладная математика» для студентов специальности «Компьютерные системы и сети» Раздел «Решение задач целочисленного линейного программирования» дневной и заочной форм обучения/ Сост. Балакирева И.А., Скатков А.В.– Севастополь: Изд-во СевНТУ, 2000. –13 с. 2. Методические указания к индивидуальным занятиям и подготовке к курсовой работе по разделу «Решение задач линейного программирования и анализ оптимального решения на ЭВМ» дисциплины «Прикладная математика» для студентов специальности 7.091501 «Компьютерные системы и сети» дневной формы обучения /Сост. Л.П. Луговская, Н.А. Скаткова. – Севастополь: Изд-во СевНТУ, 2009. – 15 с. 3. Реклейтис Г., Рейвиндран А., Регсдел К. Оптимизация в технике: в 2-х томах. Пер. с англ./ Г. Реклейтис,- М.: Наука, 1984.- Т.1.- 352 с. – Т.2.- 320 с.
Содержание
Введение ..3 1. Линейное программирование. ....4 1.1. Построение математической модели ЗЛП.. ....4 1.2. Решение ЗЛП графическим методом. ....5 1.3. Решение ЗЛП алгебраическим методом. ....6 1.4. Решение ЗЛП симплекс – методом. ....8 1.5. Решение ЗЛП методом искусственного базиса. ....10 2. Решение ЗЦЛП методом Гомори. ....13 3. Булевское программирование. Метод Баллаша. ....18 4. Поиск глобального экстремума функции…... ....20 4.1. Метод Хука – Дживса. ....20 4.2. Метод градиентного спуска с поятоянным шагом. ....26 5. Одномерная минимизация…. ....27 6. Дополнительное задание. ....32 Заключение. ....39 Список используемой литературы…. ....40 Введение В последние годы все большее значение приобретает математический подход к задачам планирования. Первые работы в этом направлении были сделаны в России ещё в 1937 году. Основной задачей математического планирования в то время была “Оптимизация перевозки угля к узлам реализации за минимальную цену”. Первым её рассматривал русский учёный Л.В. Контарович, авторство которого получило мировое признание. C помощью методов прикладной математики (в частности линейного программирования) решаются такие проблемы, как оптимизация транспортных перевозок, задача о наилучшем использовании сырья, наилучшем плане работы вычислительного комплекса, и многие другие задачи. Решение этих задач позволит значительно снизить экономические затраты на реализацию и эксплуатацию соответствующих проектов. Таким образом, задачи прикладной математики имеют самое обширное применение в жизни. В данной курсовой работе необходимо решить ряд вышеописанных задач, используя методы линейного программирования и безусловной оптимизации. Так же в дополнительном задании для решения задачи используется программа Excel.
Линейное программирование |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2019-05-07; Просмотров: 169; Нарушение авторского права страницы
0 x3 = -3x1 – 5x2 + 25
- 5x1 - 7x2 ≥ -21
-5x1 – 7x2 + 21 = x3
x3 = 21 – ( 5x1 + 7x2 )
x2
X3
λ = - 22/3
U2
5x1 + 7x2 ≤ 21
5x1 + 7x2 ≤ 21
x3 = 21 – ( 5x1 + 7x2 )
-F = 0 – ( x1 + 2x2 ) à min
x5
F =129/22
F=27/5
. Однако применение такого метода для данных задач в ряде случаев оказывается нецелесообразным. Существуют специальные методы частичного перебора для решения таких задач, наиболее совершенный из них называется аддитивным алгоритмом Баллаша с фильтром.