Решение методом искусственного базиса

Стр 1 из 4Следующая ⇒

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСТИТЕТ

Кафедра кибернетики и вычислительной техники

Пояснительная записка

К курсовой работе по дисциплине

"Прикладная математика"

Выполнила:

Студентка гр. М –22д

Чернокуцатова С.А

№ зачётной книжки:

100908(Вариант 19)

Севастополь

2012

Содержание

Введение ..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.

Линейное программирование

Построение математической модели ЗЛП

Восстанавливаем ограничения по графику:

AB (0,2) (0,5) x1 = 0

BC (0,5) (5,2)

-3x1 = 5x2 -25

Для определения знака неравенства, возьмем точку внутри области (2;2).

Получим, -6 -15 следовательно: -3x1 - 5x2 + 25 0

CD (5,2) (3,0)

-2x1 + 10 = -2x2 + 4

Для определения знака неравенства, возьмем точку внутри области (2;2).

Получим, 6 0 следовательно: -2x1 + 2x2 + 6 0

DE (3,0) (1,1)

x1 – 3 = - 2x2

Для определения знака неравенства, возьмем точку внутри области (2;2).

Получим, - 1 - 4 следовательно: x1 + 2x2 – 3 0

EA (1,1) (0,2)

x1 – 1 = - x2 +1

Для определения знака неравенства, возьмем точку внутри области (2;2).

Получим, 1 - 1 следовательно: x1 + x2 – 2 0

Получим уравнение целевой функции:

ЦФ (4,2)(3,0)

-2x1 + 8 = - x2 + 2

F = - 2x1 + x2 = - 6

Делаем вывод, что целевая функция принадлежит к семейству прямых, которые описываются уравнением: F = - 2x1 + x2

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

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

Запишем ограничения в виде системы неравенств:

F = - 2x1 + x2 à min

-3x1 - 5x2 + 25 0

-2x1 + 2x2 + 6 0

x1 + 2x2 – 3 0

x1 + x2 – 2 0

F = - 2x1 + x2 à min

1.2. Решение ЗЛП графическим методом:

F(A) = 2 F(D) = -6

F(B) = 5 à max F(E) = -1

F(C) = -8

Находим оптимальное решение графически: двигаемся по направлению градиента, пока не выйдем из области, ограниченной неравенствами (симплекса). Оптимальное решение: (5;2), F (5,2) = -2 * 5 + 2 = - 8

Значение целевой функции: - 8.
1.3. Решение ЗЛП алгебраическим методом:

Ограничения – неравенства Ограничения – равенства

-3x1 - 5x2 + 25 0 - 3x1 – 5x2 + 25 = x3

-2x1 + 2x2 + 6 0 - 2x1 + 2x2 + 6 = x4

x1 + 2x2 – 3 0 x1 + 2x2 – 3 = x5 x1 + x2 – 2 0 x1 + x2 – 2 = x6

xi 0

F = - 2x1 + x2 à min Свободные х₁, х₂

< 0, 0, 25, 6,- 3, - 2 >

Недопустимое решение, так как не выполнятся условие неотрицательности для х5 (не может быть выбрано в качестве опорного).

F = - 2x1 + x2 à min

Для приведения данного решения к допустимому выведем переменную x5 из базиса и заменим её на x1.

Заменим x1 на x3

x1 = x5 -2x2 +3

Свободные х₂,х₅

x3 = -3x5 + 6x2 – 5x2 - 9 + 25

x4= -2(x5 – 2x2 + 3) + x2 + 6

x1 = x5 – 2x2 + 3

x6 = x5 – 2x2 + 3 + x2 – 2

x3 = -3x5 + x2 +16 à 16/3

x4= - 2x5 + 6x2 à 0

x1 = x5 – 2x2 + 3 à ∞ (1)

x6 = x5 – x2 + 1 à ∞

F = -2(x5 – 2x2 + 3) + x2 = - 2x5 + 4x2 – 6 + x2 = - 2x5 + 5x2 – 6

< 3, 0, 16, 0, 0, 1 >

Допустимое (1) , может быть опорным

F = - 2x5 + 5x2 – 6 à min

Решение не является оптимальным, так как коэффициент при х₅ отрицателен. Переведём переменную х₅ в свободные. Заменим х₅на х₄

x5 =1/2 x4 + 3x2

Свободные х₄,х₂

x3 = -3(-1/2 x4 + 3x2) + x2 + 16

x5= - 1/2 x4 + 3x2

x1 = - 1/2 x4 + 3x2 – 2x2 + 3

x6 = - 1/2 x4 + 3x2 – x2 + 1

x3 = 3/2 x4 – 8x2 + 16 à2

x5= - 1/2 x4 + 3x2 à ∞

x1 = - 1/2 x4 + x2 + 3 à ∞

x6 = - 1/2 x4 + 2x2 + 1 à ∞

F = -2(- 1/2 x4 + 3x2) + 5x2 - 6= x4 – x2 – 6

< 3, 0, 16, 0, 0, 1 >

Решение не является оптимальным, так как коэффициент при х₂ отрицателен. Переведём переменную х₂ в свободные. Заменим х₂на х₃

x2 = 3/16 x4 – 1/8 x3 + 2

Свободные х₄,х₂

x2 = 3/16 x4 – 1/8 x3 + 2

x5= - 1/2 x4 + 3(3/16 x4 – 1/8 x3 + 2)

x1 = - 1/2 x4 + 3/16 x4 – 1/8 x3 + 2 + 3

x6 = - 1/2 x4 + 2(3/16 x4 – 1/8 x3 + 2) + 1

x2 = 3/16 x4 – 1/8 x3 + 2

x5= - 1/16 x4 – 1/8 x3 + 6

x1 = - 5/16 x4 – 1/8 x3 + 5

x6 = - 1/2 x4 – 1/4 x2 + 5

F = x4 – 3/16 x4 + 1/8 x3 – 2 – 6 = 13/16 x4 + 1/8 x3 – 8

< 5, 2, 0, 0, 6, 5 >

F =13/16 x4 + 1/8 x3 – 8 – все коэффициенты положительны, решение оптимальное в точке (5;2), значение исходной целевой функции - 8.

1.4. Решение ЗЛП симплекс – методом:

Для решения симплекс методом воспользуемся опорным решением (1), полученным ранее.

x3 = -3x5 + x2 +16

x4= - 2x5 + 6x2

x1 = x5 – 2x2 + 3 (1)

x6 = x5 – x2 + 1

F = - 2x5 + 5x2 – 6 à min

Преобразуем систему для решения симплекс – методом

x3 = 16 - (3x5 - x2)

x4= 0 - (2x5 - 6x2)

x1 = 3 - (-x5 + 2x2) (1)

x6 = 1 - (-x5 + x2)

F = - 6 – ( 2x5 – 5x2) à min

Таблица 1. Симплекс – таблица

Б\Св	β		x5		x2
x3	16	0	3	-3/2	-1	9
x4	0	0	2	1/2	-6	-3
x1	3	0	-1	1/2	2	-3
x6	1	0	-1	1/2	1	-3
F	-6	0	2	-1	-5	6

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

16/3 –допустимое значение, но не минимальное

0 – допустимое, минимальное

-3 – недопустимое значение (отрицательное)

- 1 – недопустимое значение (отрицательное)

Минимальным из допустимых значений является значение, соответствующее 0 поэтому генеральным элементом является элемент а₂₂(соответствует сроке х₄), тогда соответственно λ = 1/ а₂₂= 1/2. На основании этого производим вычисления.

После вычисление получаем:

Таблица2.

Б\Св	β		x4		x2
x3	16	2	-3/2	-3/16	8	1/8
x5	0	6	1/2	-9/16	-3	3/8
x1	3	2	1/2	-3/16	-1	1/8
x6	1	4	1/2	-3/8	-2	1/4
F	-6	-2	-1	3/16	1	-1/8

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

2– допустимое, минимальное

0 – допустимое, но коэффициент x5 - отрицательный

-3 – недопустимое значение (отрицательное)

-1 – недопустимое значение (отрицательное)

Минимальным из допустимых значений является значение, соответствующее 2 поэтому генеральным элементом является элемент а₂₃(соответствует сроке х₅), тогда соответственно λ = 1/ а₁₃= 1/8. На основании этого производим вычисления.

После вычисление получаем:

Таблица3.

Б\Св	β	x4	x3
x2	2	-3/16	1/8
x5	6	1/16	3/8
x1	5	5/16	1/8
x6	5	1/2	1/4
F	-8	-13/16	-1/8

Так как все коэффициенты целевой функции отрицательны, то решение оптимальное и в точке (5;2). Значение целевой функции – 8 .

< 5, 2, 0, 0, 6, 5>

В результате получили решение, аналогичное решению, полученному при использовании алгебраического метода, из чего делаем вывод о правильности полученного решения.

Решение методом искусственного базиса

Ограничения – неравенства Ограничения – равенства

-3x1 - 5x2 + 25 0 x3 = -3x1 – 5x2 + 25

-2x1 + 2x2 + 6 0 x4 = - 2x1 + 2x2 + 6

x1 + 2x2 – 3 0 ξ1 = -x1 – 2x2 + x5 +3 x1 + x2 – 2 0 ξ2 = - x1 – x2 + x6 + 2

xi 0, xi 0, ξ1 0

F = - 2x1 + x2 à min ʄ = - 2x1 – 3x2 + x5 + x6 + 5

Свободные х₁, х₂

Преобразуем систему для решения симплекс – методом

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)

	β	x1	x2	x5	x6
x3	25 -15/4	3 -5/4	5 -5/2	0 5/4	0 0
x4	6 3/2	2 1/2	-2 1	0 1/2	0 0
ξ1	3 3/2	1 1/2	2 1/2	-1 -1/2	0 0
ξ2	2 -3/4	1 -1/4	1 -1/2	0 1/4	-1 0
F	0 3/4	2 1/4	-1 1/2	0 -1/4	0 0
ʄ	5 -9/4	2 -3/4	3 -3/2	-1 3/4	-1 0

	β	x1	x5	x6
x3	85/4	7/4	5/4	0
x4	15/2	5/2	1/2	0
x2	3/2	3/2	-1/2	0
ξ2	5/4	3/4	1/4	-1
F	3/4	9/4	-1/4	0
ʄ	11/4	5/4	-1/4	-1

На данном этапе все свободные члены равны дробным числам, следовательно данный способ не может быть использован для решения данной задачи.

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

Решить ЗЦЛП

3.1Решение ЗЦЛП методом Гомори:

F = x1 + 2x2à max

5x1 + 7x2 ≤ 21

-x1 + 3x2 ≤ 8

x1,x2 ≥ 0

x1, x2 –целые

Приведём к канонической форме

-F = - x1 - 2x2 à min

- 5x1 - 7x2 ≥ -21

x1 - 3x2 ≥ - 8

Решим с помощью симплекс – метода

-5x1 – 7x2 + 21 = x3

x1 – 3x2 + 8 = x4

x3 = 21 – ( 5x1 + 7x2 )

x4 = 8 – ( -x1 + 3x2 )

-F = 0 – ( x1 + 2x2 ) àmin

	β	x1	x2
x3	21 -56/3	5 7/3	7 -7/3
x4	8 8/3	-1 -1/3	3 1/3
-F	0 -16/3	1 2/3	2 -2/3

λ = 1/3

	β	x1	X4
x3	7/3 7/22	22/3 3/22	-7/3 -7/22
X2	8/3 7/66	-1/3 1/22	1/3 -7/66
-F	-16/3 -35/66	5/3 -5/22	-2/3 35/66

λ = 3/22

	β	X3	X4
X1	7/22	3/22	-7/22
X2	61/22	1/22	5/22
-F	-129/22	-5/22	-3/22

F _опт= 129/22

X^T={ 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 )

	β	X3	X4
X1	7/22 -7/22	3/22 1	-7/22 -15/22
X2	61/22 -7/66	1/22 1/3	5/22 -5/22
U1	-7/22 7/3	-3/22 -22/3	-15/22 5
-F	-129/22 35/66	-5/22 -5/3	-3/22 25/22

λ = - 22/3

	β	U1	X4
X1	0 7/15	1 -22/15	-1 1/5
X2	8/3 0	1/3 0	0 0
X3	7/3 7/15	-22/3 -22/15	5 1/5
-F	-16/3 -7/15	-5/3 22/15	1 -1/5

λ = 1/5

	β	U1	X3
X1	7/15	-7/15	1/5
X2	8/3	1/3	0
X4	7/15	-22/15	1/5
-F	-29/5	-1/5	-1/5

F_опт = 29/5

X^T={ 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 )

	β	U1	X3
X1	7/15 14/5	-7/15 -7/5	1/5 0
X2	8/3 -2/3	1/3 1	0 0
X4	7/15 44/15	-22/15 -22/5	1/5 0
U2	-2/3 2	-1/3 -3	0 0
-F	-2 9/5 6/15	-1/5 -3/5	-1/5 0

λ = -3

	β	U2	X3
X1	7/5	-7/5	1/5
X2	2	1	0
X4	17/15	-22/5	1/5
U1	2	-3	0
-F	-2 7/5	-3/5	-1/5

Fопт = 27/5

X^T={ 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 )

	β	U2	X3
X1	7/5 -2/5	-7/5 -3/5	1/5 1
X2	2 0	1 0	0 0
X4	17/15 -2/5	-22/5 -3/5	1/5 1
U1	2 0	-3 0	0 0
U3	-2 /5 2	-3/5 3	-1/5 -5
-F	-2 7/5 2/5	-3/5 3/5	-1/5 -1

λ = -5

	β	U2	U3
X1	1	-2	1
X2	2	1	0
X4	3	-5	1
U1	2	-3	0
X3	2	3	-5
-F	-5	0	-1

F опт = 5

X^T={ 1, 2 , 2 , 3}

Дата добавления: 2018-10-27; просмотров: 245; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 Следующая ⇒

Мы поможем в написании ваших работ!