Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения

Методические указания по изучению методов математического программирования

СОДЕРЖАНИЕ

Общие рекомендации по использованию программного обеспечения____________4

Элементарные преобразования матриц. Метод Гаусса_________________________6

Задача линейного программирования. Симплекс – метод_______________________9

Задача линейного программирования. Модифицированный симплекс – метод____13

Задача линейного программирования. Двойственный симплекс – метод_________15

Транспортная задача. Метод потенциалов__________________________________18

Транспортная задача с ограниченными пропускными способностями. Метод потенциалов.________________________________________________________________22

Задача о наикратчайшем пути в сети. Метод Минти__________________________28

Задача о максимальном потоке в сети. Метод Форда – Фалькерсона_____________30

Задача целочисленного линейного программирования. Метод Гомори – 1________33

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

Метод Гомори – 2_______________________________________________________36

Задача целочисленного линейного программирования. Метод Гомори – 3________39

Задача частично дискретного линейного программирования. Метод Дальтона - Ллевелина_______42

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

Задача о назначении. Венгерский метод____________________________________49

Задача о назначении. Метод Мака_________________________________________52

Матричные игры. Связь с задачей линейного программирования. Метод Брауна – Робинсона_____________________________________________________________53

Методы одномерной оптимизации_________________________________________56

Задача выпуклого квадратичного программирования, Квадратичный симплекс - метод___________________________________________________________________59

Задача безусловной оптимизации. Метод наискорейшего спуска_______________64

 

Литература____________________________________________________________65

Общие рекомендации к использованию

Программного обеспечения

М Е Т О Д Ы О П Т И М И З А Ц И И Линейное программирование Нелинейное программирование

ЭЛЕМЕНТАРНЫЕ ПРЕОБРАЗОВАНИЯ МАТРИЦ. МЕТОД ГАУССА

Постановка задачи.

a11x1 + . . . + a1n xn = a10 . . . . . . . . . . . . . . . . . . . . . . (1.1) am1x1 + . . . + amnxn = am0

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД

в стандартной форме (СЗЛП). Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (2.1)

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

МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.

Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенаправленное перебирание ДБР, к множеству… В МСМ в отличие от СМ симплекс-превращение применяются только к базисной части… Признак оптимума и условия отсутствия оптимального решения ЗЛП для МСМ и СМ одинаковые.

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

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного программирования (МКЗЛП), которая… Найти вектор x = (x1...,xn), что минимизирует линейную функцию L(x)= c1x1 + ... + cnxn (4.1)

ТРАНСПОРТНАЯ ЗАДАЧА. МЕТОД ПОТЕНЦИАЛОВ

Постановка транспортной задачи.

Математическая модель транспортной задачи имеет вид: L(x)= c11 x11 +...+ c1n x1n +...+ cm1 xm1 +...+ cmn xmn ® min xi1 +...+ xin = ai, i=1...,m

Основные определения.

Последовательность коммуникаций, среди которых нет одинаковых, вида:  

Свойства транспортной задачи.

2. Ранг матрицы А ограничений транспортной задачи равняется m+n–1, в результате чего допустимое базисное решение задачи содержит не более m+n–1… 3. Если в транспортной задаче все числа ai, i=1...,m, bj, j=1...,n — цели, то…

Основные теоремы.

2. ДБР x=(xij, i=1...,m, j=1...,n) оптимальный тогда и только затем, когда существуют потенциалы ui, vj такие, что vj – ui = сіj, если xij - базисная перевозка vj – ui £ сіj, если xij - небазисная перевозка.

Методы поиска выходного ДБР.

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

1. a1<b1, тогда x11=a1 и вычеркивается 1-я строка таблицы; 2. a1>b1, тогда x11=b1 и вычеркивается 1-й столбец таблицы; 3. a1=b1, тогда x11=a1=b1 и вычеркивается как 1-я строка, так и 1-й столбец. В последнем случае в одну из вычеркнутых…

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

Метод отличается от предыдущего тем, что вместо северо-западной клеточки на каждом шагу выбирается клеточка с наименьшим значением транспортных расходов с_іj.

Метод вычеркивания.

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

Алгоритм метода потенциалов.

2. В дальнейшем метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n,… ii) Вычисляются оценки переменных xij для всех небазисных клеточек (і,j) за формулой Dij=cij–vj+ui (оценки базисных…

Программное обеспечение.

Задание. Решить методом потенциалов транспортные задачи, условия которых задаются…   3) ab 10 40 20 60 20 4) ab 70 …

ТРАНСПОРТНАЯ ЗАДАЧА С ОГРАНИЧЕННЫМИ ПРОПУСКНЫМИ

СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ

пропускными способностями (ТЗО). В пункте Pi (i=1...,m) производится ai единиц некоторого продукта, а в пункте… Математическая модель ТЗО имеет вид:

Свойства ТЗО и основные теоремы.

2. Решение ТЗО является базисным, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл). 3. ДБР x=(xij, i=1...,m, j=1...,n) оптимальный тогда и только затем, когда… vj – ui = сіj, если xij - базисная перевозка

Метод поиска выходного ДБР.

Выходной ДБР ТЗО (в отличие от ТЗ без ограничений), если он существует, находится существенно более сложно. Его поиск проводится в два этапа.

Первый этап (предыдущий) напоминает метод минимального элемента в ТЗ без ограничений и в общем случае не дает допустимого решения.

Второй этап содержит ряд итераций метода потенциалов, который применяется к некоторой расширенной ТЗО, построенной за результатами первого этапа.

Выходной ДБР ТЗО. 1 этап.

Возлагают . Если , то вычеркивают i1-й строку транспортной таблицы. Если , то вычеркивают j1-й столбец транспортной таблицы.

Выходной ДБР ТЗО. II этап.

xi,n+1 = ai – ( xi1 +...+ xin ), i=1...,m xm+1,j = bj – ( x1j +...+ xmj ), j=1...,n. Пометим

Потенциалы.

Указанная система содержит m+n–1 уравнений (за числом базисных клеточек) та m+n переменных. Поэтому одна из переменных задается произвольно…

Оценки.

Текущий ДБР X=||xij||, i=1...,m, j=1...,n, оптимальный, когда Dij=0, если xij - базисная перевозка Dij³0, если xij = 0, небазисная перевозка

Цикл. Метод вычеркивания.

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

Новый ДБР.

Пусть клеточка (i0,j0), для которой Находится цикл, что образуется этими клеточками. Цикл разбивается на… q1 = min{xij} по C–,

Алгоритм метода потенциалов.

2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы ui, i=1...,m, и vj, j=1...,n; ii) Вычисляются оценки Dijпеременных xij, i=1...,m, j=1...,n;

Программное обеспечение.

Обучающий модуль, с помощью которого транспортная задача с ограниченными пропускными способностями коммуникаций Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить методом потенциалов транспортные задачи, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи:

1)		6	2	5	3			16	34	15	19
	C =	3	6	9	7	,	R =	13	17	12	4	,
		7	1	6	5			17	19	2	4

а = (74, 33, 19), b = (28, 70, 15, 13);

 

2)		2	1	5	5			13	10	31	15
	C =	2	3	7	4	,	R =	20	28	7	22	,
		9	5	7	1			19	6	15	8

а = (63, 72, 17), b = (33, 40, 43, 36);

 

3)		3	6	6	4			5	8	6	4
	C =	3	2	2	6	,	R =	29	24	15	17	,
		1	4	10	7			20	5	10	6

а = (13, 79, 34), b = (49, 30, 22, 25);

 

4)		5	1	2	7			4	12	5	5
	C =	6	1	8	7	,	R =	20	10	37	10	,
		2	9	4	10			25	10	10	15

а = (20, 76, 54), b = (40, 30, 52, 28);

 

5)		9	6	6	1			15	10	34	7
	C =	8	10	9	2	,	R =	31	23	20	11	,
		5	9	2	6			11	15	4	10

а = (64, 75, 21), b = (57, 33, 44, 26);

 

6)		6	4	8	5			20	5	15	12
	C =	2	8	3	2	,	R =	45	20	21	19	,
		1	7	2	8			8	20	12	4

а = (42, 99, 27), b = (68, 40, 30, 30);

 

7)		5	6	10	3			37	20	7	21
	C =	6	4	7	2	,	R =	5	26	7	11	,
		8	8	3	7			5	20	25	10

а = (78, 37, 53), b = (38, 60, 30, 40);

 

8)		6	1	9	3			16	30	21	30
	C =	9	2	9	7	,	R =	18	4	5	11	,
		3	2	10	6			30	4	29	15

а = (77, 24, 70), b = (56, 30, 40, 45);

 

9)		8	4	6	8			12	20	30	20
	C =	8	9	9	6	,	R =	25	4	3	2	,
		9	10	4	7			33	10	30	10

а = (72, 29, 68), b = (65, 24, 50, 30);

 

10)		1	3	8	7			10	26	23	8
	C =	9	4	5	10	,	R =	6	18	30	5	,
		9	7	2	8			9	2	25	3

а = (53, 45, 38), b = (21, 30, 75, 10).

Ответы:

1) L(x*)= 444. 2) L(x*)= 538. 3) L(x*)= 413. 4) L(x*)= 837. 5) L(x*)= 1091.

6) L(x*)= 700. 7) L(x*)= 800. 8) L(x*)= 885. 9) L(x*)= 1134. 10) L(x*)= 649.

 

Лабораторная работа 7.

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ

На сети, что задается графом (I,U), где И — множество вершин, U — множество дуг, с определенной на ней функцией стоимости сіj ((і,j) — дуга с U),… L = ((i1,i2),(i2,i3)...,(is-1,is)) из вершины i1 в вершину is, длина которого

ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ НА СЕТИ.

МЕТОД ФОРДА-ФАЛКЕРСОНА

На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией пропускных способностей rij ((і,j) —… Алгоритм Форда-Фалкерсона применяется для построения максимального потока на… Будем считать, что вершиной-источником является 1-я вершина, вершиной-стоком — вершина с номером n.

ЗАДАЧА ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

МЕТОД ГОМОРИ-1

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

L(x)= c1x1 + ... + cnxn (9.1) и удовлетворяет систему ограничений a11x1 + . . . + a1n xn = a10

Изложение метода Гомори-1.

Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9.4) отбрасыванием условия целочисленности переменных (9.4). Если… Пусть на последней итерации симплекс-метода при решении вспомогательной ЗЛП… xi + а¢і,m+1 xm+1 +...+ а¢in xn = а¢i0, i=1...,m

Алгоритм метода Гомори-1.

2. Пусть на s-й итерации развязана вспомогательная ЗЛП, что имеет M ограничений и N переменных, x(s) — ее оптимальное решение. Будем считать, что x(s) определяется каноничными ограничениями последней… xi + bi,M+1 xM+1 +...+ biN xN = bi0, i=1...,M

Программное обеспечение.

Обучающий модуль, с помощью которого полностью целочисленная задача линейного программирования Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.

Задание.

Решить методом Гомори-1 задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые и целые.

 

1)	5 x1 + 6 x2 + 6 x3 ® min	2)	6 x1 + 4 x2 ® min
	2 x1 + 4 x2 ³ 10		2 x1 + x2 ³ 3
	3 x1 + 2 x2 + 2 x3 ³ 10;		x1 – x2 £ 1;

 

3)	6 x1 + 4 x2 ® min	4)	x1 + x2 ® min
	2 x1 + x2 ³ 3		– x1 – x2 + x5 = –1
	x1 – 2 x2 £ 2		–2 x1 + 2 x2 + x3 = –2
	3 x1 + 2 x2 ³ 1;		–4 x1 + 2 x2 + x4 = –1;

 

 

5)	6 x1 + 4 x2 ® min	6)	2 x1 + 3 x2 ® min
	2 x1 + x2 ³ 3		x1 + 2 x2 ³ 16
	x1 – x2 ³ 1;		2 x1 + x2 ³ 16;

 

7)	5 x1 – 3 x2 ® max	8)	5 x2 + 7 x4 ® min
	3 x1 + 2 x2 ³ 6		– 10 x2 + x3 + x4 = –16
	2 x1 – 3 x2 ³ – 6		x1 – 3 x2 – 3 x4 = –12
	x1 – x2 £ 4		– 6 x2 – 2 x4 + x5 = –17;

 

9)	– 5 x4 – 7 x5 ® max	10)	8 x1 + 2 x2 ® max
	x1 – x4 – 2 x5 = – 7		x1 – 4 x2 + x3 = 4
	– x3 + 3 x4 – 6 x5 = – 3		– 4 x1 + x2 + x4 = 4
	x2 – x4 – 4 x5 = –11;		x1 + x2 + x5 = 6.

 

Ответы:

1) x* = (3; 1; 0), L(x*)= 21.

2) x* = (1; 1), L(x*)= 10.

3) x* = (1; 1), L(x*)= 10.

4) x* = (1; 0; 0; 3; 0), L(x*)= 1.

5) x* = (2; 0), L(x*)= 12.

6) x* = (6; 5), L(x*)= 27.

7) x* = (18; 14), L(x*)= 48.

8) x* = (0; 4; 24; 0; 7), L(x*)= 20.

9) x* = (0; 0; 0; 3; 2), L(x*)= -29.

10) x* = (5; 1; 0; 0; 0), L(x*)= 42.

 

Лабораторная работа 10.

ЗАДАЧА ЧАСТИЧНО ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2

Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (10.1) и удовлетворяет систему ограничений

ЗАДАЧА ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАМУВАННЯ.

МЕТОД ГОМОРИ-3

Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (11.1) и удовлетворяет систему ограничений

7.

Задание.

Решить методом Гомори-3 задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые и целые.

 

1)	– x1 – 5 x2 ® max	2)	3 x1 + 2 x2 ® min	3)	x1 + 3x2 ® min
	12 x1 – 3 x2 ³ 8		– 3 x2 £ 2		x1 + 6x2 ³ 5
	– 3 x1 + 9 x2 ³ 8		– 2 x1 + 2 x2 £ 2		– 5x1 + 19x2 ³ 13
	– x1 + 3 x2 ³ 3;		2 x1 – x2 ³ 1;		– 3x1 + 6x2 ³ 2;

 

4)	7x1 + 12x2 ® min	5)	–3x1 – 8x2 ® max	6)	10x1 + 7x2 ® min
	4x1 – 23x2 £ –14		–2x1 + 10x2 ³ 4		2x1 – 12x2 £ –9
	–12x1 + 2x2 £ –9		–3x1 – 5x2 £ –10		x1 + 4x2 ³ 10
	–13x1 – x2 £ –10;		2x1 – x2 ³ 2;		4x1 – 2x2 ³ 14;

 

7)	– 3 x4 – 2 x5 ® max	8)	3 x2 + x5 ® min
	x1 – 5 x4 + x5 = –15		– 2 x2 + x3 – 18 x5 = –20
	x3 + x4 – 8 x5 = – 9		x1 + x2 – 15 x5 = – 7
	x2 – x4 – 10 x5 = –19;		– 5 x2 + x4 + x5 = – 9.

Ответы:

1) x* = (2; 2), L(x*)= –12.

2) x* = (1; 0), L(x*)= 3.

3) x* = (0; 1), L(x*)= 3.

4) x* = (1; 1), L(x*)= 19.

5) x* = (2; 1), L(x*)= –14.

6) x* = (5; 2), L(x*)= 64.

7) x* = (3; 5; 3; 4; 2), L(x*)= –16.

8) x* = (6; 2; 2; 0; 1), L(x*)= 7.

 

Лабораторная работа 12.

ЗАДАЧА ЧАСТИЧНО ДИСКРЕТНОГО ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА

Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (12.1) и удовлетворяет систему ограничений

ЗАДАЧА ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

МЕТОД ВЕТВЕЙ И ГРАНИЦ.

Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (13.1) и удовлетворяет систему ограничений

Изложение метода Ленд-Дойга.

Пусть некоторая координата xj(0;1) (j=1...,n) решения x(0;1) не является целочисленной. В этом случае осуществляется разветвление множества D(0;1)… Для последующего разветвления выбирается перспективное множество D(k;r) с…

Алгоритм метода Ленд-Дойга.

2. Решаются вспомогательные ЗЛП на множествах D(k;r). Пусть x(k;r) — оптимальные решения указанных ЗЛП. 3. Вычисляются границы на множествах D(k;r) за формулой x(k;r)= ]L(x(k;r))[,… 4. Если существуют k, l такие, что x(k;l) — целочисленное решение и для всех веток r на k-у шаге выполняются…

Программное обеспечение.

Обучающий модуль, с помощью которого задача целочисленного линейного программирования. Решается в диалоге с пользователем за выбранным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить методом ветвей и границ задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи (без использования программного обеспечения).

Во всех задачах выполняются условия: x_j³0, x_j — целое, j=1,2.

 

1)	x1 + x2 ® max	2)	–2 x1 – x2 ® min	3)	6 x1 + 4 x2 ® min
	2 x1 + 11 x2 £ 38		6 x1 + 4 x2 £ 24		2 x1 + x2 ³ 3
	x1 + x2 £ 7		x1 – x2 £ 3		x1 – 2 x2 £ 2
	4 x1 – 5 x2 £ 5;		– x1 + 3 x2 £ 3;		3x1 + 2x2 ³ 1;

 

4)	x1 + x2 ® min	5)	5 x1 + 7 x2 ® min	6)	2 x1 – x2 ® max
	– x1 – x2 £ – 1		– 10 x1 + x2 £ – 16		2 x1 + x2 £ 8
	– 2 x1 + 2 x2 £ – 2		– 3 x1 – 3 x2 £ – 12		x1 + 3 x2 ³ 6
	– 4 x1 + 2 x2 £ – 1;		– 6 x1 – 2 x2 £ – 17		3 x1 + x2 ³ 3;

 

 

7)	x1 + 4 x2 ® min	8)	–5 x1 – 7 x2 ® max	9)	x1 + 2 x2® min
	x1 – 3 x2 £ –1		2 x1 + x2 ³ 3		2 x1 + 2 x2 ³ 5
	8 x1 – x2 ³ 6		20 x1 – x2 ³ 15		x1 – 3 x2 £ –1
	3 x1 – 11 x2 £ –7;		x1 – x2 £ –2;		x1 – x2 ³ 2.

Ответы:

1) x* = (3; 2) или x* = (2; 3), L(x*)= 5.

2) x* = (3; 1), L(x*)= –7.

3) x* = (1; 1), L(x*)= 10.

4) x* = (1; 0), L(x*)= 1.

5) x* = (4; 0), L(x*)=20.

6) x* = (3; 1), L(x*)= 5.

7) x* = (1; 1), L(x*)= 5.

8) x* = (1; 3), L(x*)= –26.

9) x* = (4; 2), L(x*)= 8.

Лабораторная работа 14.

ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД

Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию L(X)= c11 x11 +...+ c1n x1n +...+ cn1 xn1 +...+ cnn xnn (14.1) и удовлетворяет систему ограничений

Отнимаем от каждого элемента j-го столбца преобразованной матрицы расходов его минимальный элемент (j=1...,n). В результате выполнения двух пунктов каждая строка и каждый столбец матрицы расходов имеют по крайней мере один 0.

3. Просматриваем последовательно строки матрицы расходов, начиная с первого. Если строка имеет лишь один необозначенный 0, помечаем его отметкой * но зачеркиваем (с помощью отметки ^) остальных нулей в этом же столбце. 0 считается обозначенным, если он имеет отметку*. Повторяем эти действия, пока каждая строка не будет иметь необозначенных нулей, или будет иметь их по крайней мере два.

4. Действия п. 3 повторяем для всех столбцов матрицы расходов.

5. Действия п.п. 3 и 4 повторяем последовательно (если необходимо) пока не случится один из трех возможных случаев:

i) каждая строка имеет назначение (имеет 0 с отметкой *);

ii) есть по крайней мере два необозначенных нуля в некоторых строках и некоторых столбцах матрицы расходов;

iii) нет необозначенных нулей и полное назначение еще не получено (число нулей с отметкой * меньше n).

В случае и) задача об оптимальных назначениях развязана: xij, что отвечают 0*, равняются 1, остальные — 0, конец. В случае ii) произвольно выбираем один из необозначенных нулей, помечаем его отметкой *, зачеркиваем остальных нулей в той же строке и в том же столбце и возвращаемся к п. 3. В случае iii) переходим к п. 7.

7. Помечаем отметкой # строки, для которых не полученное назначение (в которых нет 0*). Такие строки считаем обозначенными, остальные — необозначенными. Аналогично называются и столбцы матрицы расходов.

8. Помечаем отметкой # еще необозначенные столбцы, которые имеют зачеркнутый 0 (обозначен отметкой ^) в обозначенных строках.

9. Помечаем отметкой # еще необозначенные строки, которые имеют назначение (то есть 0*) в обозначенных столбцах.

10. Повторяем действия п.п. 8 и 9 до тех пор, пока больше нельзя будет пометить ни одну строку и столбец матрицы расходов.

11. Вычеркиваем (с помощью отметки &) необозначенные строки и обозначенные столбцы матрицы расходов.

12. Находим минимальный невычеркнутый элемент матрицы расходов, отнимаем его от элементов каждой из невычеркнутых строк, добавляем к элементам всех вычеркнутых столбцов и переходим к п. 3. При этом отметки элементов матрицы расходов (* но ^) теряют свою силу.

Замечание.

1. Если в задаче об оптимальных назначениях (14.1)–(14.4) целевую функцию (14.1) нужно максимизировать, то для ее решения можно применить венгерский метод, заменив матрицу C на –C.

2. За определением в задаче об оптимальных назначениях матрица расходов квадратная. Если матрица C не является квадратной, то она превращается к такой добавлением необходимого числа дополнительных строк или столбцов с соответствующими элементами cij=0. В 1-м случае работы, что получили оптимальные назначения в дополнительных строках, остаются без исполнителей. В 2-м — исполнители, которые получили оптимальные назначения в дополнительных столбцах, остаются без работы.

Программное обеспечение.

Обучающий модуль, с помощью которого задача об оптимальных назначениях решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить венгерским методом задачи об оптимальных назначениях, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи с матрицами расходов C:

 

1)	3	4	2	8	1	7	3	2)	6	2	15	2	4	9	5
	2	3	13	9	1	6	2		12	11	1	13	8	11	13
	12	4	12	5	3	1	4		3	2	12	9	10	14	1
	5	6	1	7	11	8	6		7	1	3	4	5	6	8
	11	4	10	10	5	13	7		8	9	14	3	11	18	12
	9	6	11	12	7	1	2		1	7	5	6	15	16	2
	2	4	8	5	9	3	10		13	10	4	7	10	16	17

 

3)	5	17	5	12	11	6	4	4)	21	7	2	12	15	2	17
	10	9	6	10	12	16	4		23	15	24	20	12	5	11
	9	3	2	8	13	14	8		17	24	4	17	2	22	15
	13	1	7	11	7	18	19		19	7	8	1	13	14	4
	1	7	12	8	3	1	5		15	6	6	14	19	3	16
	3	11	13	9	14	20	21		23	6	5	19	15	11	19
	10	2	6	6	15	15	22		16	18	22	22	1	1	7

 

5)	2	4	5	10	4	6	8	6)	7	9	4	6	4	12	3
	3	6	4	13	6	7	9		2	4	4	7	8	8	5
	4	7	10	5	10	4	5		4	5	6	5	12	7	3
	6	5	12	4	7	5	4		3	6	8	4	6	6	7
	7	4	13	6	6	7	5		5	10	9	3	8	5	4
	10	8	5	2	8	9	10		6	9	5	10	9	6	7
	11	9	4	8	4	5	4		7	4	3	6	2	5	4

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

7)	6	7	8	9	10	12	5	8)	12	4	8	9	12	4	5
	2	3	4	8	9	16	8		6	5	10	7	3	6	8
	9	6	3	6	8	9	3		3	10	4	12	5	6	10
	5	7	6	7	10	7	8		11	12	16	5	7	8	12
	4	8	18	8	6	2	3		6	7	4	6	7	2	1
	12	9	2	10	8	4	5		12	5	7	12	9	4	5
	3	10	3	5	4	3	8		4	6	8	4	3	6	7

 

9)	6	3	5	4	6	7	8	10)	4	3	5	4	8	9	10
	5	2	4	3	8	9	10		7	6	2	5	12	13	4
	4	3	3	5	4	6	7		6	5	1	6	7	8	9
	7	5	3	2	1	4	5		7	4	6	10	4	7	3
	8	6	6	10	12	5	4		4	3	10	8	5	3	2
	12	7	8	7	4	8	9		3	8	12	6	3	6	12
	4	8	9	6	7	4	3		5	9	4	7	8	9	1

 

Ответы:

1) L(x*)= 16. 2) L(x*)= 24. 3) L(x*)= 25. 4) L(x*)= 38. 5) L(x*)= 24.

6) L(x*)= 25. 7) L(x*)= 81. 8) L(x*)= 73. 9) L(x*)= 60. 10) L(x*)= 68.

Лабораторная работа 15.

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА

Алгоритм метода Мака. 1. Помечаем минимальный элемент строки отметкой *. Если минимальных элементов… 2. Действия п. 1 повторяем для всех строк матрицы расходов.

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

7. Помечаем (отметкой &) столбцы, которые имеют больше одного обозначенного элемента. Они образуют множество В, другие столбцы матрицы расходов образуют множество А.

8. Просматриваем последовательно строки матрицы расходов, начиная с первого, и находим строку, в которой элемент с отметкой * принадлежит множеству В.

9. Находим для строки минимальную разницу между элементами множества. Но и элементом с отметкой *.

10. Действия п.п. 8 и 9 повторяем последовательно для всех строк, которые имеют свойства, которые указаны в п. 8.

11. Выбираем наименьшую из минимальных разниц.

12. Добавляем это число к каждому элементу множества В.

13. Возвращаемся к п. 3.

Замечания те же самые, как в предыдущем разделе.

Программное обеспечение.

Обучающий модуль, с помощью которого задача об оптимальных назначениях Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.

Задание.

Решить методом Мака задачи об оптимальных назначениях, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также задачи, матрице расходов C которых заданы в предыдущем разделе.

Лабораторная работа 16.

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН

Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданной платежной матрицей C=||cij||,… Основные определения и теоремы. Смешанные стратегии игроков I1 и I2 — это векторы x=(x1...,xm) и y=(y1...,yn)', компоненты которых удовлетворяют…

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМIЗАЦИИ

Метод золотого сечения.

В начале вычислений возлагают А{0}= А, B{0}= B. На s-у шаге определяют величины L{s}= B{s} – G(B{s} – А{s})

Метод случайного поиска.

В программе рассматривается реализация данного метода для функции одной переменной. Произвольная функция F(x) задана на промежутке [A,B]. С помощью датчика… Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к глобальному минимуму функции, что…

Метод дихотомии (половинного деления).

Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума. В начале вычислений возлагают А{0}= А, B{0}= B. На s-у шаге определяют величины

Программное обеспечение.

Обучающий модуль, с помощью которого задачи одномерной оптимизации Решаются в диалоге с пользователем за выложенными алгоритмами, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

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

1) F(x)=

X2–1|–1|–1| x Î [–2, 2]; 2) F(x)= 2x3–3x2–12x+1++ x Î [–2, 2]; 3) F(x)= (x+1)2 ln(x+1)+x exp(–x) x Î [0, e]; 4) F(x)= sin(x) sin(2x)+ arccos(x2) x Î [–0.75, 0.75]; 5) F(x)= arctg(x) – ln(x) /2 x Î [0.65, 1.75]; 6) F(x)= x+ + ехp(x) x2 x Î [0, 4]; 7) F(x)= 4 x/(x2 + 4)–[x2 (x – 2)](2/5) x Î [–2, 2].   Лабораторная работа 18.

ЗАДАЧА ВЫПУКЛОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ.

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД

Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию F(x)= F(x1...,xn) (18.1) и удовлетворяет систему ограничений

ЗАДАЧА БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.

МЕТОД САМОГО БЫСТРОГО СПУСКУ

Постановка задачи безусловной оптимизации.

Найти вектор x=(x₁...,xn), что минимизирует (максимизирует) функцию

F(x)=F(x1...,xn).

Градиентные методы безусловной оптимизации.

x[s+1]= x[s]– r[s] ÑF(x[s]) где ÑF(.) — градиент функции F(.), который задается соотношением  

Метод самого быстрого спуска.

F(x[s]–r [s]ÑF(x[s])) = min(F(x[s]–rÑF(x[s]))) где минимум берется по всем r>0. При некоторых условиях x[s] следует к стационарной точке функции F(x), если s следует к бесконечности.

Задание.

Решить методом самого быстрого спуска задачи безусловной оптимизации, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9).

Лiтература

2. Ю.Д.Попов. Линейное и нелинейное программирование. Киев, УМК ВО, 1988. 3. Ф.П.Васильев. Численные методы решения экстремальных задач. Москва,… 4. И.Л.Калихман. Сборник задач по математическому программированию. Москва, «Высшая школа», 1975.