Методы оптимизации

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых»

«Управление и информатика в технических и экономических системах»

КУРСОВАЯ РАБОТА

«Методы оптимизации»

Вариант №4

Владимир, 2014



Содержание

1. Задача о кратчайших путях в графе

2. Задача о критическом пути в графе

3. Задача о максимальном патоке в графе

4. Задача об оптимальном распределении заданного потока в транспортной сети

5. Задача линейного программирования, решаемая графическим методом

6. Решение задачи ЛП симплекс-методом

7. Несбалансированная транспортная задача

8. Численные методы решения одномерных задач статической оптимизации



1. Задача о кратчайших путях в графе

	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X1		13	13	4	24
X2			4						28
X3				19					4
X4					21	9		15
X5							1
X6							21	21	5	15
X7										8
X8									25	14
X9										28
X10

1) Исход: X1

2) Строим график



3)Запишем шаги

X1->X4 l=4

X1->X2 l=13

X1->X3 l=13

X4

X1->X6 l=13

X3

X1->X9 l=17

X4

X1->X8 l=19

X1->X5 l=24

X7

X1->X7 l=25

X4 ,X6

X1->X10 l=28

	1	2	3	4	5	6	7	8	9	10
1	0	-	-	-	-	-	-	-	-	-
2	0	13	13	4	24	-	-	-	-	-
3	0	13	13	4	24	13	-	19	-	-
4	0	13	13	4	24	13	-	19	12	-
5	0	13	13	4	24	13	-	19	17	-
6	0	13	13	4	24	13	34	19	17	-
7	0	13	13	4	24	13	34	19	17	45
8	0	13	13	4	24	13	34	19	17	33
9	0	13	13	4	24	13	25	19	17	33
10	0	13	13	4	24	13	25	19	17	33



2. Задача о критическом пути в графе

Ответ: C1 -> C2 -> C3 -> C9 -> C8 -> C10 -> C12 -> C13 = 61

3. Задача о максимальном патоке в графе

1)Строим рисунок.



2) S=X1 (исход) B=X6 (сход)

S = (7+9) = 16

B = (7+1+8) = 16

Ответ: 16.

4. Задача об оптимальном распределении заданного потока в транспортной сети

1) Строим граф



P=0,8

2) Находим P0 =16*0,8=12,8

3)Решаем.

3.1)

Lk = (X1,X3,X6)=9

Ck = (7,7) = 7

Q1 = 9*7 = 7

P = 7

Pk = 12,8 - 7 = 5,8.

3.2)

Lk = (X1,X2,X4,X6) = 16.

Lk = (9,8,13) = 8

Q = 16*7 = 112

P = 5,8

Pk = 5,8 - 5,8 = 0

4) Строим новый граф

5) Расписываем шаги

P1,3 = 7 P1,2 = 5,8

P3,6 = 7 P2,4 = 5,8

P4,6 = 5,8

5. Задача линейного программирования, решаемая графическим методом

Необходимо найти минимальное значение целевой функции F = -x1+2x2 > min, при системе ограничений:

x1-x2?3	(1)
2x1-3x2?0	(2)
2x1-x2=4	(3)

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

Размещено на http://www.allbest.ru/

Или



Размещено на http://www.allbest.ru/

Границы области допустимых решений

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

Обозначим границы области многоугольника решений.



Размещено на http://www.allbest.ru/

Рассмотрим целевую функцию задачи F = -x1+2x2 > min.

Построим прямую, отвечающую значению функции F = 0: F = -x1+2x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (-1; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.



Размещено на http://www.allbest.ru/

Область допустимых решений представляет собой многоугольник

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

x1-x2=3

2x1-x2=4

Решив систему уравнений, получим: x1 = 1, x2 = -2

Откуда найдем минимальное значение целевой функции:

F(X) = -1*1 + 2*(-2) = -5

	x1	x2		B
	3	2
F(x)	-1	-2	0	=>	-7
1	1	-2	<=	3	-1
2	2	-3	>=	0	0
3	2	-1	=	4	4

поток распределение транспортный оптимизация

6. Решение задачи ЛП симплекс-методом

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

Определим максимальное значение целевой функции F(X) = - x1 + x2 - 2x3 + 3x4 + x5 при следующих условиях-ограничений.

x1 + 2x2 - x3 - 2x4 + x5?3

- x1 - x2 + x3 + 2x4 + x5?1

2x1 + x2 + x3 - x4?1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x6. В 2-м неравенстве смысла (?) вводим базисную переменную x7. В 3-м неравенстве смысла (?) вводим базисную переменную x8.

1x1 + 2x2-1x3-2x4 + 1x5 + 1x6 + 0x7 + 0x8 = 3

-1x1-1x2 + 1x3 + 2x4 + 1x5 + 0x6 + 1x7 + 0x8 = 1

2x1 + 1x2 + 1x3-1x4 + 0x5 + 0x6 + 0x7 + 1x8 = 1

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1	2	-1	-2	1	1	0	0
-1	-1	1	2	1	0	1	0
2	1	1	-1	0	0	0	1

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

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x6, x7, x8

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,0,3,1,1)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	3	1	2	-1	-2	1	1	0	0
x7	1	-1	-1	1	2	1	0	1	0
x8	1	2	1	1	-1	0	0	0	1
F(X0)	0	1	-1	2	-3	-1	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai4

и из них выберем наименьшее:

min (- , 1 : 2 , - ) = Ѕ

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	3	1	2	-1	-2	1	1	0	0	-
x7	1	-1	-1	1	2	1	0	1	0	1/2
x8	1	2	1	1	-1	0	0	0	1	-
F(X1)	0	1	-1	2	-3	-1	0	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x7 в план 1 войдет переменная x4.

Строка, соответствующая переменной x4 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=2

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x4 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x4 и столбец x4.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
3-(1 * -2):2	1-(-1 * -2):2	2-(-1 * -2):2	-1-(1 * -2):2	-2-(2 * -2):2	1-(1 * -2):2	1-(0 * -2):2	0-(1 * -2):2	0-(0 * -2):2
1 : 2	-1 : 2	-1 : 2	1 : 2	2 : 2	1 : 2	0 : 2	1 : 2	0 : 2
1-(1 * -1):2	2-(-1 * -1):2	1-(-1 * -1):2	1-(1 * -1):2	-1-(2 * -1):2	0-(1 * -1):2	0-(0 * -1):2	0-(1 * -1):2	1-(0 * -1):2
0-(1 * -3):2	1-(-1 * -3):2	-1-(-1 * -3):2	2-(1 * -3):2	-3-(2 * -3):2	-1-(1 * -3):2	0-(0 * -3):2	0-(1 * -3):2	0-(0 * -3):2

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	4	0	1	0	0	2	1	1	0
x4	1/2	-1/2	-1/2	1/2	1	1/2	0	1/2	0
x8	3/2	3/2	1/2	3/2	0	1/2	0	1/2	1
F(X1)	3/2	-1/2	-5/2	7/2	0	1/2	0	3/2	0

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

min (4 : 1 , - , 11/2 : 1/2 ) = 3

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (1/2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	4	0	1	0	0	2	1	1	0	4
x4	1/2	-1/2	-1/2	1/2	1	1/2	0	1/2	0	-
x8	11/2	11/2	1/2	11/2	0	1/2	0	1/2	1	3
F(X2)	11/2	-1/2	-21/2	31/2	0	1/2	0	11/2	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x8 в план 2 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x8 плана 1 на разрешающий элемент РЭ=1/2

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x2 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
4-(11/2 * 1):1/2	0-(11/2 * 1):1/2	1-(1/2 * 1):1/2	0-(11/2 * 1):1/2	0-(0 * 1):1/2	2-(1/2 * 1):1/2	1-(0 * 1):1/2	1-(1/2 * 1):1/2	0-(1 * 1):1/2
1/2-(11/2 * -1/2):1/2	-1/2-(11/2 * -1/2):1/2	-1/2-(1/2 * -1/2):1/2	1/2-(11/2 * -1/2):1/2	1-(0 * -1/2):1/2	1/2-(1/2 * -1/2):1/2	0-(0 * -1/2):1/2	1/2-(1/2 * -1/2):1/2	0-(1 * -1/2):1/2
11/2 : 1/2	11/2 : 1/2	1/2 : 1/2	11/2 : 1/2	0 : 1/2	1/2 : 1/2	0 : 1/2	1/2 : 1/2	1 : 1/2
11/2-(11/2 * -21/2):1/2	-1/2-(11/2 * -21/2):1/2	-21/2-(1/2 * -21/2):1/2	31/2-(11/2 * -21/2):1/2	0-(0 * -21/2):1/2	1/2-(1/2 * -21/2):1/2	0-(0 * -21/2):1/2	11/2-(1/2 * -21/2):1/2	0-(1 * -21/2):1/2

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	1	-3	0	-3	0	1	1	0	-2
x4	2	1	0	2	1	1	0	1	1
x2	3	3	1	3	0	1	0	1	2
F(X2)	9	7	0	11	0	3	0	4	5

5. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	1	-3	0	-3	0	1	1	0	-2
x4	2	1	0	2	1	1	0	1	1
x2	3	3	1	3	0	1	0	1	2
F(X3)	9	7	0	11	0	3	0	4	5

Оптимальный план можно записать так:

x4 = 2

x2 = 3

F(X) = 3*2 + 1*3 = 9

	x1	x2	x3	x4	x5		B
	0	3	0	2	0
F(x)	-1	1	-2	3	1	0	=>	9
1	1	2	-1	-2	1	<=	3	2
2	-1	-1	1	2	1	<=	1	1
3	2	1	1	-1	0	<=	1	1



7. Несбалансированная транспортная задача

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

	1	2	3	4	Запасы
1	3	8	4	5	60
2	7	3	8	4	52
3	8	4	2	6	52
Потребности	27	40	43	41

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 60 + 52 + 52 = 164

?b = 27 + 40 + 43 + 41 = 151

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 13 (164--151). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	3	8	4	5	0	60
2	7	3	8	4	0	52
3	8	4	2	6	0	52
Потребности	27	40	43	41	13

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 3

Для этого элемента запасы равны 60, потребности 27. Поскольку минимальным является 27, то вычитаем его.

x11 = min(60,27) = 27.

3	8	4	5	0	60 - 27 = 33
x	3	8	4	0	52
x	4	2	6	0	52
27 - 27 = 0	40	43	41	13	0

Искомый элемент равен 8

Для этого элемента запасы равны 33, потребности 40. Поскольку минимальным является 33, то вычитаем его.

x12 = min(33,40) = 33.

3	8	x	x	x	33 - 33 = 0
x	3	8	4	0	52
x	4	2	6	0	52
0	40 - 33 = 7	43	41	13	0

Искомый элемент равен 3

Для этого элемента запасы равны 52, потребности 7. Поскольку минимальным является 7, то вычитаем его.

x22 = min(52,7) = 7.

3	8	x	x	x	0
x	3	8	4	0	52 - 7 = 45
x	x	2	6	0	52
0	7 - 7 = 0	43	41	13	0

Искомый элемент равен 8

Для этого элемента запасы равны 45, потребности 43. Поскольку минимальным является 43, то вычитаем его.

x23 = min(45,43) = 43.

3	8	x	x	x	0
x	3	8	4	0	45 - 43 = 2
x	x	x	6	0	52
0	0	43 - 43 = 0	41	13	0

Искомый элемент равен 4

Для этого элемента запасы равны 2, потребности 41. Поскольку минимальным является 2, то вычитаем его.

x24 = min(2,41) = 2.

3	8	x	x	x	0
x	3	8	4	x	2 - 2 = 0
x	x	x	6	0	52
0	0	0	41 - 2 = 39	13	0

Искомый элемент равен 6

Для этого элемента запасы равны 52, потребности 39. Поскольку минимальным является 39, то вычитаем его.

x34 = min(52,39) = 39.

3	8	x	x	x	0
x	3	8	4	x	0
x	x	x	6	0	52 - 39 = 13
0	0	0	39 - 39 = 0	13	0

Искомый элемент равен 0

Для этого элемента запасы равны 13, потребности 13. Поскольку минимальным является 13, то вычитаем его.

x35 = min(13,13) = 13.

3	8	x	x	x	0
x	3	8	4	x	0
x	x	x	6	0	13 - 13 = 0
0	0	0	0	13 - 13 = 0	0

	1	2	3	4	5	Запасы
1	3[27]	8[33]	4	5	0	60
2	7	3[7]	8[43]	4[2]	0	52
3	8	4	2	6[39]	0[13]	52
Потребности	27	40	43	41	13

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*27 + 8*33 + 3*7 + 8*43 + 4*2 + 6*39 + 0*13 = 952

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 3; 0 + v1 = 3; v1 = 3

u1 + v2 = 8; 0 + v2 = 8; v2 = 8

u2 + v2 = 3; 8 + u2 = 3; u2 = -5

u2 + v3 = 8; -5 + v3 = 8; v3 = 13

u2 + v4 = 4; -5 + v4 = 4; v4 = 9

u3 + v4 = 6; 9 + u3 = 6; u3 = -3

u3 + v5 = 0; -3 + v5 = 0; v5 = 3

	v1=3	v2=8	v3=13	v4=9	v5=3
u1=0	3[27]	8[33]	4	5	0
u2=-5	7	3[7]	8[43]	4[2]	0
u3=-3	8	4	2	6[39]	0[13]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;3): 0 + 13 > 4; ?13 = 0 + 13 - 4 = 9

(1;4): 0 + 9 > 5; ?14 = 0 + 9 - 5 = 4

(1;5): 0 + 3 > 0; ?15 = 0 + 3 - 0 = 3

(3;2): -3 + 8 > 4; ?32 = -3 + 8 - 4 = 1

(3;3): -3 + 13 > 2; ?33 = -3 + 13 - 2 = 8

max(9,4,3,1,8) = 9

Выбираем максимальную оценку свободной клетки (1;3): 4

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[27]	8[33][-]	4[+]	5	0	60
2	7	3[7][+]	8[43][-]	4[2]	0	52
3	8	4	2	6[39]	0[13]	52
Потребности	27	40	43	41	13

Цикл приведен в таблице (1,3 > 1,2 > 2,2 > 2,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 33. Прибавляем 33 к объемам грузов, стоящих в плюсовых клетках и вычитаем 33 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[27]	8	4[33]	5	0	60
2	7	3[40]	8[10]	4[2]	0	52
3	8	4	2	6[39]	0[13]	52
Потребности	27	40	43	41	13

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 3; 0 + v1 = 3; v1 = 3

u1 + v3 = 4; 0 + v3 = 4; v3 = 4

u2 + v3 = 8; 4 + u2 = 8; u2 = 4

u2 + v2 = 3; 4 + v2 = 3; v2 = -1

u2 + v4 = 4; 4 + v4 = 4; v4 = 0

u3 + v4 = 6; 0 + u3 = 6; u3 = 6

u3 + v5 = 0; 6 + v5 = 0; v5 = -6

	v1=3	v2=-1	v3=4	v4=0	v5=-6
u1=0	3[27]	8	4[33]	5	0
u2=4	7	3[40]	8[10]	4[2]	0
u3=6	8	4	2	6[39]	0[13]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(3;1): 6 + 3 > 8; ?31 = 6 + 3 - 8 = 1

(3;2): 6 + -1 > 4; ?32 = 6 + -1 - 4 = 1

(3;3): 6 + 4 > 2; ?33 = 6 + 4 - 2 = 8

max(1,1,8) = 8

Выбираем максимальную оценку свободной клетки (3;3): 2

Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[27]	8	4[33]	5	0	60
2	7	3[40]	8[10][-]	4[2][+]	0	52
3	8	4	2[+]	6[39][-]	0[13]	52
Потребности	27	40	43	41	13

Цикл приведен в таблице (3,3 > 3,4 > 2,4 > 2,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[27]	8	4[33]	5	0	60
2	7	3[40]	8	4[12]	0	52
3	8	4	2[10]	6[29]	0[13]	52
Потребности	27	40	43	41	13

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 3; 0 + v1 = 3; v1 = 3

u1 + v3 = 4; 0 + v3 = 4; v3 = 4

u3 + v3 = 2; 4 + u3 = 2; u3 = -2

u3 + v4 = 6; -2 + v4 = 6; v4 = 8

u2 + v4 = 4; 8 + u2 = 4; u2 = -4

u2 + v2 = 3; -4 + v2 = 3; v2 = 7

u3 + v5 = 0; -2 + v5 = 0; v5 = 2

	v1=3	v2=7	v3=4	v4=8	v5=2
u1=0	3[27]	8	4[33]	5	0
u2=-4	7	3[40]	8	4[12]	0
u3=-2	8	4	2[10]	6[29]	0[13]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;4): 0 + 8 > 5; ?14 = 0 + 8 - 5 = 3

(1;5): 0 + 2 > 0; ?15 = 0 + 2 - 0 = 2

(3;2): -2 + 7 > 4; ?32 = -2 + 7 - 4 = 1

max(3,2,1) = 3

Выбираем максимальную оценку свободной клетки (1;4): 5

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[27]	8	4[33][-]	5[+]	0	60
2	7	3[40]	8	4[12]	0	52
3	8	4	2[10][+]	6[29][-]	0[13]	52
Потребности	27	40	43	41	13

Цикл приведен в таблице (1,4 > 1,3 > 3,3 > 3,4).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 29. Прибавляем 29 к объемам грузов, стоящих в плюсовых клетках и вычитаем 29 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[27]	8	4[4]	5[29]	0	60
2	7	3[40]	8	4[12]	0	52
3	8	4	2[39]	6	0[13]	52
Потребности	27	40	43	41	13

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 3; 0 + v1 = 3; v1 = 3

u1 + v3 = 4; 0 + v3 = 4; v3 = 4

u3 + v3 = 2; 4 + u3 = 2; u3 = -2

u3 + v5 = 0; -2 + v5 = 0; v5 = 2

u1 + v4 = 5; 0 + v4 = 5; v4 = 5

u2 + v4 = 4; 5 + u2 = 4; u2 = -1

u2 + v2 = 3; -1 + v2 = 3; v2 = 4

	v1=3	v2=4	v3=4	v4=5	v5=2
u1=0	3[27]	8	4[4]	5[29]	0
u2=-1	7	3[40]	8	4[12]	0
u3=-2	8	4	2[39]	6	0[13]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;5): 0 + 2 > 0; ?15 = 0 + 2 - 0 = 2

(2;5): -1 + 2 > 0; ?25 = -1 + 2 - 0 = 1

max(2,1) = 2

Выбираем максимальную оценку свободной клетки (1;5): 0

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[27]	8	4[4][-]	5[29]	0[+]	60
2	7	3[40]	8	4[12]	0	52
3	8	4	2[39][+]	6	0[13][-]	52
Потребности	27	40	43	41	13

Цикл приведен в таблице (1,5 > 1,3 > 3,3 > 3,5).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[27]	8	4	5[29]	0[4]	60
2	7	3[40]	8	4[12]	0	52
3	8	4	2[43]	6	0[9]	52
Потребности	27	40	43	41	13

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 3; 0 + v1 = 3; v1 = 3

u1 + v4 = 5; 0 + v4 = 5; v4 = 5

u2 + v4 = 4; 5 + u2 = 4; u2 = -1

u2 + v2 = 3; -1 + v2 = 3; v2 = 4

u1 + v5 = 0; 0 + v5 = 0; v5 = 0

u3 + v5 = 0; 0 + u3 = 0; u3 = 0

u3 + v3 = 2; 0 + v3 = 2; v3 = 2

	v1=3	v2=4	v3=2	v4=5	v5=0
u1=0	3[27]	8	4	5[29]	0[4]
u2=-1	7	3[40]	8	4[12]	0
u3=0	8	4	2[43]	6	0[9]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj <= cij.

Минимальные затраты составят:

F(x) = 3*27 + 5*29 + 0*4 + 3*40 + 4*12 + 2*43 + 0*9 = 480

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (27), в 4-й магазин (29)

Из 2-го склада необходимо груз направить в 2-й магазин (40), в 4-й магазин (12)

Из 3-го склада необходимо весь груз направить в 3-й магазин

На 1-ом складе остался невостребованным груз в количестве 4 ед.

Оптимальный план является вырожденным, так как базисная переменная x15=0.

На 3-ом складе остался невостребованным груз в количестве 9 ед.

Оптимальный план является вырожденным, так как базисная переменная x35=0.

Стоимости перевозок
Поставщики			Потребители
	1	2	3	4	5
A	3	8	4	5	0
B	7	3	8	4	0
C	8	4	2	6	0
Неизвестные
	1	1	1	1	1	5	60
	1	1	1	1	1	5	52
	1	1	1	1	1	5	52
	3	3	3	3	3
	27	40	43	41	13
Функция цели
	480

8. Численные методы решения одномерных задач статической оптимизации

1) Метод золотого сечения в Excel
N	a	b	b-a	a+i*c	a+k*c	F(l)	F(m)
1	-2	1	3	-0,854	-0,146	-0,49384	-0,14295
2	-2	-0,146	1,854	-1,29177	-0,854	-0,48405	-0,49384
3	-1,29177	-0,146	1,145772	-0,854	-0,58368	-0,49384	-0,43536
4	-1,29177	-0,58368	0,708087	-1,02128	-0,854	-0,49989	-0,49384
5	-1,29177	-0,854	0,437772	-1,12454	-1,02128	-0,49658	-0,49989
6	-1,12454	-0,854	0,270543	-1,02128	-0,95735	-0,49989	-0,49953
7	-1,12454	-0,95735	0,167196	-1,06067	-1,02128	-0,49913	-0,49989
8	-1,06067	-0,95735	0,103327	-1,02128	-0,99682	-0,49989	-0,5
9	-1,02128	-0,95735	0,063935	-0,99682	-0,98177	-0,5	-0,49992
10	-1,02128	-0,98177	0,039512	-1,00619	-0,99682	-0,49999	-0,5
11	-1,00619	-0,98177	0,024418	-0,99682	-0,9911	-0,5	-0,49998
12	-1,00619	-0,9911	0,015091	-1,00042	-0,99682	-0,5	-0,5
13	-1,00619	-0,99682	0,009371	-1,00261	-1,00042	-0,5	-0,5
14	-1,00261	-0,99682	0,005791	-1,00042	-0,99903	-0,5	-0,5
15	-1,00261	-0,99903	0,003579	-1,00124	-1,00042	-0,5	-0,5
16	-1,00124	-0,99903	0,002212	-1,00042	-0,99988	-0,5	-0,5
17	-1,00042	-0,99903	0,001394	-0,99988	-0,99956	-0,5	-0,5
18	-1,00042	-0,99956	0,000861	-1,0001	-0,99988	-0,5	-0,5
19	-1,00042	-0,99988	0,000549	-1,00021	-1,0001	-0,5	-0,5

2) Метод золотого сечения С#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.IO;

namespace ConsoleApplication1

{

class Program

{

static double fg(double x)

{

double mf = x / (1 + (x * x));

return mf;

}

static void Main(string[] args)

{

const double e = 0.001; // точность

double gold = ((1 + Math.Sqrt(5)) / 2); // пропорция "Золотого Сечения"

double a = -2, b = 1; // начало и конец отрезка

double x1 = 0, x2 = 0; // точки деления

double y1 = 0, y2 = 0; // значение целевой функции в точках деления

double f;

int n = 0; // число итераций

do

{

n++;

x1 = b - ((b - a) / gold);

x2 = a + ((b - a) / gold);

y1 = fg(x1);

y2 = fg(x2);

if (y1 >= y2) { a = x1; } else { b = x2; }

Console.WriteLine("Процесс вычисления №" + n + "отрезок от а до б (" + a + " : " + b + ") значение функции на интервале: " + y1 + " : " + y2);

f = b - a;

} while (Math.Round(f, 3) >= e);

Console.WriteLine("Точка минимума: " + (x1+x2)/2);

Console.WriteLine("Значение функции в точка минимума: " + (y1+y2)/2);

Console.WriteLine("Результат получен за: " + n + " итераций.");

Console.ReadKey();

}

}

}

Процесс вычисления №1отрезок от а до б (-2 : -0,145898033750316) значение функции на интервале: -0,493846095040953 : -0,142857142857143

Процесс вычисления №2отрезок от а до б (-1,29179606750063 : -0,145898033750316) значение функции на интервале: -0,48404770824998 : -0,493846095040953

Процесс вычисления №3отрезок от а до б (-1,29179606750063 : -0,583592135001262) значение функции на интервале: -0,493846095040953 : -0,43532816449453

Процесс вычисления №4отрезок от а до б (-1,29179606750063 : -0,854101966249684) значение функции на интервале: -0,499889109598277 : -0,493846095040953

Процесс вычисления №5отрезок от а до б (-1,12461179749811 : -0,854101966249684) значение функции на интервале: -0,496571787514389 : -0,499889109598277

Процесс вычисления №6отрезок от а до б (-1,12461179749811 : -0,957427527495584) значение функции на интервале: -0,499889109598277 : -0,499527196176926

Процесс вычисления №7отрезок от а до б (-1,06075308874148 : -0,957427527495584) значение функции на интервале: -0,499131624599642 : -0,499889109598277

Процесс вычисления №8отрезок от а до б (-1,02128623625221 : -0,957427527495584) значение функции на интервале: -0,499889109598277 : -0,499997581281123

Процесс вычисления №9отрезок от а до б (-1,02128623625221 : -0,981819383762934) значение функции на интервале: -0,499997581281123 : -0,499915850312333

Процесс вычисления №10отрезок от а до б (-1,00621124003028 : -0,981819383762934) значение функции на интервале: -0,499990414844916 : -0,499997581281123

Процесс вычисления №11отрезок от а до б (-1,00621124003028 : -0,991136243808359) значение функции на интервале: -0,499997581281123 : -0,499980183587142

Процесс вычисления №12отрезок от а до б (-1,00621124003028 : -0,996894379984858) значение функции на интервале: -0,499999948697475 : -0,499997581281123

Процесс вычисления №13отрезок от а до б (-1,00265251616136 : -0,996894379984858) значение функции на интервале: -0,499998245698987 : -0,499999948697475

Процесс вычисления №14отрезок от а до б (-1,00265251616136 : -0,99909379229243) значение функции на интервале: -0,499999948697475 : -0,499999794510766

Процесс вычисления №15отрезок от а до б (-1,0012932046 : -0,99909379229243) значение функции на интервале: -0,499999582445798 : -0,499999948697475

Процесс вычисления №16отрезок от а до б (-1,00045310385378 : -0,99909379229243) значение функции на интервале: -0,499999948697475 : -0,499999998907395

Процесс вычисления №17отрезок от а до б (-1,00045310385378 : -0,999613003107567) значение функции на интервале: -0,499999998907395 : -0,499999962543859

Процесс вычисления №18отрезок от а до б (-1,0001322139227 : -0,999613003107567) значение функции на интервале: -0,499999995630448 : -0,499999998907395

Процесс вычисления №19отрезок от а до б (-1,0001322139227 : -0,999811323991623) значение функции на интервале: -0,499999998907395 : -0,499999991098662

Точка минимума: -0,999872608515135

Значение функции в точка минимума: -0,499999995003028

Результат получен за: 19 итераций.

Размещено на Allbest.ru