Другие предметы \ Исследование операций и методы оптимизации

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

Страницы работы

33 страницы (Word-файл)

Скачать файл

Фрагмент текста работы

Если – недопустимая точка, уменьшать в два раза расстояния до центра

тяжести, пока не станет допустимой точкой.

Проверка окончания поиска :

вычисления оканчиваются, иначе переход к п. II. 1).

Для невыпуклых областей метод расходится.

Задание № 1

Методы решения задач транспортного типа.

4 вариант.

1) Математическая постановка транспортной задачи.

Имеется четыре поставщика продукции (А₁, А_2,А_3, А₄), в руках которых сосредоточены 24, 14, 19 и 17 единиц соответственно. Необходимо доставить продукцию пятерым потребителям (В_1,В_2,В_3,В_4,В₅) в количестве 22, 9, 12, 13, 18 единиц. Известна стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

Стоимость перевозок					Запасы
22	24	25	23	29	24	А₁
1	21	10	7	19	14	А₂
2	26	18	30	27	19	А₃
22	10	29	26	23	17	А₄
22	9	12	13	18
В₁	В₂	В₃	В₄	В₅
Потребности

Аi=74

Вj=74

Аi=Вj

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

2) Поиск опорного решения транспортной задачи с помощью следующих методов:

а) Метод северо-западного угла

Исходная задача:

22	24	25	23	29	24
1	21	10	7	19	14
2	26	18	30	27	19
22	10	29	26	23	17
22	9	12	13	18	74

После преобразований:

22 ²²	2 ²⁴	0	0	0	24
0	7 ²¹	7 ¹⁰	0	0	14
0	0	5 ¹⁸	13 ³⁰	1 ²⁷	19
0	0	0	0	17 ²³	17
22	9	12	13	18	74

Стоимость перевозки: Z=1647

б) Метод минимального элемента

В исходной задаче в каждом столбце нахожу минимальный элемент и отмечаю его «*».

22	24	25	23	29	24
1 *	21	10 *	7 *	19 *	14
2	26	18	30	27	19
22	10 *	29	26	23	17
22	9	12	13	18	74

Далее заполняю таблицу, начиная с элементов, помеченных «*». Получаю:

0	0	1 ²⁵	13 ²³	10 ²⁹	24
14 ¹	0	0	0	0	14
8 ²	0	11 ¹⁸	0	0	19
0	9 ¹⁰	0	0	8 ²³	17
22	9	12	13	18	74

Стоимость перевозки Z=1116

в) Метод двойного предпочтения

Теперь ищу минимумы строк и так же отмечаю их «*»

22 *	24	25	23	29	24
1 **	21	10 *	7 *	19 *	14
2 *	26	18	30	27	19
22	10 **	29	26	23	17
22	9	12	13	18	74

Далее заполняю таблицу, начиная с элементов, помеченных «^**», затем «^*». В результате получаю:

8 ²²	0	0	13 ²³	3 ²⁹	24
14 ¹	0	0	0	0	14
0	0	12 ¹⁸	0	7 ²⁷	19
0	9 ¹⁰	0	0	8 ²³	17
22	9	12	13	18	74

Стоимость перевозки Z=1255

3) Метод потенциалов

-7

22 ²²

2 ²⁴

0 ²⁵

0 ²³

0 ²⁹

0 ¹

2 ²¹

12 ¹⁰

0 ⁷

0 ¹⁹

0 ²

0 ²⁶

0 ¹⁸

13 ³⁰

1 ²⁷

-4

0 ²²

0 ¹⁰

0 ²⁹

0 ²⁶

17 ²³

5 ²²

2 ²⁴

0 ²⁵

13 ²³

0 ²⁹

-3

0 ¹

2 ²¹

12 ¹⁰

0 ⁷

0 ¹⁹

-20

18 ²

0 ²⁶

5 ¹⁸

0 ³⁰

1 ²⁷

-24

0 ²²

0 ¹⁰

0 ²⁹

0 ²⁶

17 ²³

5 ²²

4 ²⁴

0 ²⁵

11 ²³

0 ²⁹

-16

0 ¹

0 ²¹

12 ¹⁰

2 ⁷

0 ¹⁹

-20

18 ²

0 ²⁶

0 ¹⁸

13 ³⁰

1 ²⁷

-24

0 ²²

0 ¹⁰

0 ²⁹

0 ²⁶

17 ²³

0 ²²

4 ²⁴

5 ²⁵

11 ²³

0 ²⁹

5 ¹

0 ²¹

7 ¹⁰

2 ⁷

0 ¹⁹

18 ²

0 ²⁶

0 ¹⁸

13 ³⁰

1 ²⁷

-3

0 ²²

0 ¹⁰

0 ²⁹

0 ²⁶

17 ²³

	1	9	10	7	19
15	0 ²²	4 ²⁴	5 ²⁵	11 ²³	0 ²⁹	24
0	4 ¹	0 ²¹	7 ¹⁰	2 ⁷	1 ¹⁹	14
1	19 ²	0 ²⁶	0 ¹⁸	13 ³⁰	0 ²⁷	19
4	0 ²²	0 ¹⁰	0 ²⁹	0 ²⁶	17 ²³	17
	22	9	12	13	18	74

	1	6	10	7	19
15	0 ²²	0 ²⁴	5 ²⁵	11 ²³	4 ²⁹	24
0	4 ¹	0 ²¹	7 ¹⁰	2 ⁷	1 ¹⁹	14
1	19 ²	0 ²⁶	0 ¹⁸	13 ³⁰	0 ²⁷	19
4	0 ²²	4 ¹⁰	0 ²⁹	0 ²⁶	13 ²³	17
	22	9	12	13	18	74

	1	1	10	7	14
15	0 ²²	0 ²⁴	5 ²⁵	10 ²³	5 ²⁹	24
0	4 ¹	0 ²¹	7 ¹⁰	3 ⁷	0 ¹⁹	14
1	19 ²	0 ²⁶	0 ¹⁸	13 ³⁰	0 ²⁷	19
9	0 ²²	4 ¹⁰	0 ²⁹	0 ²⁶	13 ²³	17
	22	9	12	13	18	74

Z=972

4) Венгерский метод

Находим min по столбцам и вычитаем из всех элементов этого столбца

	Матрица C
22	24	25	23	29	24
1	21	10	7	19	14
2	26	18	30	27	19
22	10	29	26	23	17
22	9	12	13	18	74

То же самое, но по строкам

	Матрица C'
21	14	15	16	10	24
0	11	0	0	0	14
1	16	8	23	8	19
21	0	19	19	4	17
22	9	12	13	18	74

	Матрица C₀
11	4	5	6	0	24
0	11	0	0	0	14
0	15	7	22	7	19
21	0	19	19	4	17
22	9	12	13	18	74

	Матрица X₀
0	0	0	0	16	24	8
3	0	7	2	2	14	0
19	0	0	0	0	19	0
0	9	0	0	0	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

₀=2*74-2*58=32>0 =>переходим к первой итерации

	Итерация №1
	Матрица C₀

+	+			+
11	4	5	6	0	24	8
0*	11	0'	0	0	14	0	+
0'	15	7	22	7	19	0
21	0	19	19	4	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

Матрица C₀

	+			+
11	4	5	6	0	24	8
0*	11	0'	0	0	14	0	+
0'	15	7	22	7	19	0	+
21	0	19	19	4	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

Существенных нулей нет.
Ищем невыделенный нуль и с самого начала I этапа

Матрица C₀

	+			+
11	4	5	6	0	24	8
0*	11	0'	0	0	14	0	+
0'	15	7	22	7	19	0	+
21	0	19	19	4	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

Т.к. не осталось больше невыд. Нулей, то переходим к III этапу

		III этап
	+			+
11	4	5	6	0	24	8
0*	11	0'	0	0	14	0	+
0'	15	7	22	7	19	0	+	Матрица C₀
21	0	19	19	4	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

Мин. Элемент среди невыд-х cтрок и столбцов: h=5

Матрица C'₀

	+			+
6	4	0	1	0	24	8
0*	16	0'	0	5	14	0	+
0'	20	7	22	12	19	0	+
16	0	14	14	4	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

Получили матрицу C₁
Переходим к I этапу

I этап

Матрица C₁

	+			+
6	4	0'	1	0	24	8
0	16	0	0	5	14	0
0	20	7	22	12	19	0
16	0	14	14	4	17	8
22	9	12	13	18	74
0	0	5	11	0		невязки

Невязка по строке б₁=8>0 => переходим ко II этапу

II этап

Цепочка состоит из одного элемента C¹₁₃=0.
Находим Q=min(8;5)=5

Матрица X₁

0	0	5	0	16	24	3
3	0	7	2	2	14	0
19	0	0	0	0	19	0
0	9	0	0	0	17	8
22	9	12	13	18	74
0	0	0	11	0		невязки

1=32-2*Q=32-2*5=22>0 Переходим ко второй итерации

Переходим ко второй итерации

Итерация №2

I этап

Матрица C₁

+	+	+		+
6	4	0'	1	0	24	3
0*	16	0	0'	5	14	0	+
0'	20	7	22	12	19	0	+
16	0	14	14	4	17	8
22	9	12	13	18	74
0	0	0	11	0		невязки

Т.к не осталось невыд-х нулей, то переходим к III этапу

III этап

Минимальный элемент среди невыд-х строк и столбцов h=1

Матрица C'₁

	+	+		+
5	4	0	0	0	24	3
0	17	1	0	6	14	0	+
0	21	8	22	13	19	0	+
15	0	14	13	4	17	8
22	9	12	13	18	74
0	0	0	11	0		невязки

Получили матрицу C_2.
Переходим к I этапу

I этап

Матрица C₂

	+	+		+
5	4	0	0'	0	24	3
0	17	1	0	6	14	0	+
0	21	8	22	13	19	0	+
15	0	14	13	4	17	8
22	9	12	13	18	74
0	0	0	11	0		невязки

Среди невыд-х столбцов находим элемент C₁₄=0, который расположен
в строке с ненулевой невязкой. =>Переходим ко II этапу

II этап

Цепочка состоит из одного элемента C²₁₄=0
Находим Q=min(3;11)=3

Матрица X₂

0	0	5	3	16	24	0
3	0	7	2	2	14	0
19	0	0	0	0	19	0
0	9	0	0	0	17	8
22	9	12	13	18	74
0	0	0	8	0		невязки

2==22-2*Q=32-2*3=16>0 Переходим к след. Итерации

Итерация №3

I этап

Матрица C₂

+	+	+		+
5	4	0	0	0	24	3	+
0	17	1	0	6	14	0	+
0	21	8	22	13	19	0	+
15	0	14	13	4	17	8
22	9	12	13	18	74
0	0	0	8	0		невязки

Т.к. не осталось невыд-х нулей, то переходим к III этапу

III этап

Мин-й элемент среди невыд-х строк и столбцов h=13

Матрица C'₂

18	17	13	0	13	24
13	30	14	0	19	14
13	34	21	22	26	19
15	0	14	0	4	17
22	9	12	13	18	74

Получили матрицу C3.

Переходим к I этапу

I этап

Матрица C₃

+	+	+		+
18	17	13	0	13	24	3	+
13	30	14	0	19	14	0	+
13	34	21	22	26	19	0	+
15	0	14	0'	4	17	8
22	9	12	13	18	74
0	0	0	8	0		невязки

Среди невыд-х элементов находим элемент C44=0, который расположен в строке с ненулевой невязкой.

Следовательно переходим ко II этапу.

II этап

Цепочка состоит из одного элемента C³₄₄=0
Находим Q=min(8;8)=8

Матрица X₃

0 ²²	0 ²⁴	5 ²⁵	3 ²³	16 ²⁹	24	0
3 ¹	0 ²¹	7 ¹⁰	2 ⁷	2 ¹⁹	14	0
19 ²	0 ²⁶	0 ¹⁸	0 ³⁰	0 ²⁷	19	0
0 ²²	9 ¹⁰	0 ²⁹	8 ²⁶	0 ²³	17	0
22	9	12	13	18	74
0	0	0	0	0		невязки

3=3=16-2*Q=16-2*8=0

Следовательно X3 - оптимальный план.

Стоимость перевозки Z=1119

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

Задание № 2.

Методы решения задач линейного и целочисленного программирования.

22 вариант.

1) Математическая постановка задачи линейного программирования.

Дана линейная функция

6х₁ + 7х₂ ® max

и система линейных ограничений:

6х₁ + 11х₂£ 66

12х₁ + 7х₂£ 84

х₁³ 0, х₂³0

Необходимо найти такие неотрицательные значения х₁и х_2, которые удовлетворяют системе ограничений и доставляют линейной функции минимальное значение.

2) Графическая интерпретация задачи линейного программирования.

1) 6x1+11x2 =66

x₁	0	11
x₂	6	0

2)12x1+7x2 =84

x₁	0	7
x₂	12	0

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

Точка А – точка максимального значения функции.

Координаты точки А находятся при решении системы линейных уравнений.

6x₁+11x₂ =66

12x₁+7x₂ =84

x₁=15,4/3=5,13

x₂=16/5=3,2

F_max=6*5,13+7*3,2=798/15=53,2

3) Двойственная задача линейного программирования и ее графическая интерпретация.

66y₁+84y₂->min

6y₁+12y₂>=6

11y₁+7y₂>=7

1)6y₁+12y₂=6

y₁

y₂

1/2

2)11y₁+7y₂=7

y₁

11/7

y₂

В результате получила область допустимых планов.

Координаты точки А находятся при решении следующей системы линейных уравнений.

6y₁+12y₂=6

11y₁+7y₂=7

y₁=7/15=2,8

y₂=4/15=0,27

F_min=66*2,8+84*0,27=798/15=266/5 =53,2

4) Симплекс-метод

а) прямая задача

6x1+7x2 ->max

6x₁+11x₂<=66

12x₁+7x₂ <=84

x₁>=0, x₂>=0

Приводим задачу к канонической форме, а целевую функцию к min:

	6x₁+11x₂+x₃=66
	12x₁+7x₂ +x₄=84
	x₁>=0, x₂>=0

V= -f = -6x₁-7x₂->min

Исходный опорный план:
X₀=(66, 84, 0, 0)

Строим исходную симплекс-таблицу

i	Базис	C	A₀	C1=-6	C2=-7	C3=0	C4=0
i	Базис	базиса	A₀	A1	A2	A3	A4
1	A3	0	66	6	11	1	0
2	A4	0	84	12	7	0	1
m+1	U_j-C_j		0	6	7	0	0

Исходный опорный план не оптимален, т.к. в (m+1) строке 2 положительных элемента

O₀₁=min(66/6;84/12)=7
O₀₁(U₁-C₁)=76=42
O₀₂=min(66/11;84/7)=6
O₀₂(U₂-C₂)=67=42
maxO_0j(U_j-C_j)=max(42;42)=42

За разрешающий элемент возьмем элемент 12 на пересечении 2-ой строки и 1-го столбца(A1)

II симплекс-таблица

i	Базис	C	A₀	C1=-6	C2=-7	C3=0	C4=0
i	Базис	базиса	A₀	A1	A2	A3	A4
1	A3	0	24	0	15/2	1	-1/2
2	A1	-6	7	1	7/12	0	1/12
m+1	U_j-C_j		-42	0	7/2	0	-1/2

Второй опорный план:
X₁=(7, 0, 24, 0)
Он не оптимален,
т.к. в (m+1) строке 1 положительный элемент

За разрешающий элемент возьмем элемент 15/2 на пересечении 1-ой строки и 2-го столбца(A2)

III симплекс-таблица

i	Базис	C	A₀	C1=-6	C2=-7	C3=0	C4=0
i	Базис	базиса	A₀	A1	A2	A3	A4
1	A2	-7	16/5	0	1	2/15	-1/15
2	A1	-6	77/15	1	0	-7/90	11/90
m+1	U_j-C_j		-266/5	0	0	-7/15	-4/15

Третий опорный план:
X₂=(77/15, 16/5, 0, 0)
Он оптимален, т.к. в (m+1) строке нет положительных элементов

f_max= -V = 266/5=53,2

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

Следовательно решение верно.

б) двойственная задача

66y₁+84y₂->min

6y₁+12y₂>=6

11y₁+7y₂>=7

Приводим задачу к канонической форме, а целевую функцию к min:

6y₁+12y₂+y₃=6

11y₁+7y₂+y₄=7

V= -f = -66y₁-84y₂->max

Исходный опорный план:
Y₀=(6, 7, 0, 0)

Строим исходную симплекс-таблицу

i	Базис	C	A₀	C1=-66	C2=-84	C3=0	C4=0
i	Базис	базиса	A₀	A1	A2	A3	A4
1	A3	0	6	6	12	1	0
2	A4	0	7	11	7	0	1
m+1	U_j-C_j		0	66	84	0	0

Исходный опорный план не оптимален, т.к. в (m+1) строке 2 положительных элемента

O₀₁=min(6/6;7/11)=7/11

O₀₁*(U₁-C₁)=7/11*66=42

O₀₂=min(6/12;7/7)=6/12=1/2

O₀₂*(U₂-C₂)=1/2*84=42

maxO_0j(U_j-C_j)=max(42;42)=42

За разрешающий элемент возьмем элемент 12 на пересечении 1-ой строки и 2-го столбца(A2)

II симплекс-таблица

i	Базис	C	A₀	C1=-66	C2=-84	C3=0	C4=0
i	Базис	базиса	A₀	A1	A2	A3	A4
1	A2	-84	1/2	1/2	1	1/12	0
2	A4	0	7/2	15/2	0	-7/12	1
m+1	U_j-C_j		-42	24	0	-7	0

Второй опорный план:
Y₁=(0, 1/2, 0, 7/2)
Он не оптимален,
т.к. в (m+1) строке 1 положительный элемент

За разрешающий элемент возьмем элемент 15/2 на пересечении 2-ой строки и 1-го столбца(A1)

III симплекс-таблица

i	Базис	C	A₀	C1=-66	C2=-84	C3=0	C4=0
i	Базис	базиса	A₀	A1	A2	A3	A4
1	A2	-84	4/15	0	1	11/90	-1/15
2	A1	-66	7/15	1	0	-7/90	2/15
m+1	U_j-C_j		-266/5	0	0	-77/15	-16/15

Третий опорный план:
Y₂=(7/15, 4/15, 0, 0)
Он оптимален, т.к. в (m+1) строке нет положительных элементов