Математика 1

<

092613 0016 11 Математика 1Задача 1.

Решить графически задачу ЛП.

Вариант 2.

092613 0016 12 Математика 1

Решение.

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

x1+2x2≤10

(1)

x1+x2≤6

(2)

2x1+x2≤10

(3)

x1≥0

(4)

x2≥0

(5)

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

092613 0016 14 Математика 1

или

092613 0016 15 Математика 1

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

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

092613 0016 16 Математика 1

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

092613 0016 17 Математика 1

Равный масштаб

092613 0016 18 Математика 1

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

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

x1+2x2≤10
x1+x2≤6

Решив систему уравнений, получим:

x1 = 2, x2 = 4

Откуда найдем максимальное значение целевой функции:
F(X) = 2*2 + 3*4 — 1 = 15

Задача 2

Вариант 6.

Решить стандартную задачу ЛП

        092613 0016 19 Математика 1

симплекс-методом.

Вариант задачи, №

c1

c2

c3

a11

a12

a13

a21

a22

a23

a31

a32

a33

b1

b2

b3

6.

4

5

8

-9

-8

-6

3

2

4

5

3

2

-40

30

20

Решение.

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

Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).

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

9x1 + 8x2 + 6x3≥40

3x1 + 2x2 + 4x3≤30

5x1 + 3x2 + 2x3≤20

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

В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.

9x1 + 8x2 + 6x3-1x4 + 0x5 + 0x6 = 40

3x1 + 2x2 + 4x3 + 0x4 + 1x5 + 0x6 = 30

5x1 + 3x2 + 2x3 + 0x4 + 0x5 + 1x6 = 20

Решение состоит из двух этапов. Первый этап — введение искусственного базиса (единичной матрицы) и поиск первого опорного плана (без учета целевой функции). Второй этап — поиск оптимального решения на основе целевой функции.

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

Имеем:

 

 

 

Матрица коэффициентов A = aij

9

8

6

-1

0

0

1

3

2

4

0

1

0

0

5

3

2

0

0

1

0

 

Матрица b.

 

Итерация №1.

Базисные переменные:

<X> = (7, 5, 6)

Выбираем столбцы под номерами(7, 5, 6) из матрицы А и формируем матрицу В.

 

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

Матрица c.

В этой матрице под номерами (7 — номера искусственных переменных) ставим (1).

c = (0, 0, 0, 0, 0, 0, 1)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(7,5,6) = (1, 0, 0)

cN(1,2,3,4) = (0, 0, 0, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

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

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (1, 0, 0)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (9, 8, 6, -1)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*1,2,3,4 = cN — uN = (-9, -8, -6, 1)

Откуда номер направляющего столбца s = 1 (индекс максимального по модулю значения из отрицательных элементов).

Выбираем из матрицы А столбец под номером 1.

 

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

Умножаем обратную матрицу B-1 на вектор (a11,…,am1)

a* = B-1 (a11,…,am1)T = (9, 0, 0)T

min(40:9 = 44/9;30:3 = 10;20:5 = 4;) = 4

Откуда номер направляющей строки r = 3 (индекс минимального значения).

Итерация №2.

Базисные переменные:

<X> = (7, 5, 1)

Выбираем столбцы под номерами(7, 5, 1) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (-9, -8, -6, 1, 0, 0, 0)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(7,5,1) = (0, 0, -9)

cN(2,3,4,6) = (-8, -6, 1, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (0, 0, -14/5)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (-52/5, -33/5, 0, -14/5)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*2,3,4,6 = cN — uN = (-23/5, -22/5, 1, 14/5)

Откуда номер направляющего столбца s = 1 (индекс максимального по модулю значения из отрицательных элементов).

Выбираем из матрицы А столбец под номером 1.

 

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

Умножаем обратную матрицу B-1 на вектор (a11,…,am1)

a* = B-1 (a11,…,am1)T = (23/5, 0, 0)T

min(4:23/5 = 17/13;18:1/5 = 90;4:3/5 = 62/3😉 = 17/13

Откуда номер направляющей строки r = 1 (индекс минимального значения).

 

Итерация №3.

Базисные переменные:

<X> = (2, 5, 1)

Выбираем столбцы под номерами(2, 5, 1) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (0, -23/5, -22/5, 1, 0, 14/5, 0)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(2,5,1) = (-23/5, 0, 0)

cN(3,4,6,7) = (-22/5, 1, 14/5, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (-1, 0, 14/5)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (-22/5, 1, 14/5, -1)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*3,4,6,7 = cN — uN = (0, 0, 0, 1)

 

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

Вектор С не содержит отрицательных элементов. Первый этап симплекс-метода завершен.

Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.

Выразим базисные переменные:

x2 = 17/13+12/13x3-5/13x4-9/13x6

x1 = 31/13-2/13x3+3/13x4+8/13x6

которые подставим в целевую функцию:

F(X) = 4(31/13-2/13x3+3/13x4+8/13x6) + 5(17/13+12/13x3-5/13x4-9/13x6) + 8x3

или

F(X) = 20+4x3+x4+x6

Имеем:

Матрица коэффициентов A = aij

 

Матрица b.

 

Итерация №1.

Базисные переменные:

<X> = (2, 5, 1)

Выбираем столбцы под номерами(2, 5, 1) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (0, 0, -4, -1, 0, -1)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(2,5,1) = (0, 0, 0)

cN(3,4,6) = (-4, -1, -1, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

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

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (0, 0, 0)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (0, 0, 0, 0)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*3,4,6 = cN — uN = (-4, -1, -1, 0)

Откуда номер направляющего столбца s = 1 (индекс максимального по модулю значения из отрицательных элементов).

Выбираем из матрицы А столбец под номером 1.

 

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

Умножаем обратную матрицу B-1 на вектор (a11,…,am1)

a* = B-1 (a11,…,am1)T = (12/13, 0, 0)T

min(17/13:12/13 = 12/3;179/13:28/13 = 613/17;-;) = 12/3

Откуда номер направляющей строки r = 1 (индекс минимального значения).

Итерация №2.

Базисные переменные:

<X> = (3, 5, 1)

Выбираем столбцы под номерами(3, 5, 1) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (0, 0, -4, -1, 0, -1)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(3,5,1) = (-4, 0, 0)

cN(2,4,6) = (0, -1, -1, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (-12/3, 0, 3)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (-41/3, 12/3, 3, 0)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*2,4,6 = cN — uN = (41/3, -22/3, -4, 0)

Откуда номер направляющего столбца s = 3 (индекс максимального по модулю значения из отрицательных элементов).

Выбираем из матрицы А столбец под номером 3.

 

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

Умножаем обратную матрицу B-1 на вектор (a13,…,am3)

a* = B-1 (a13,…,am3)T = (-3/4, 0, 0)T

min(-;131/3:11/2 = 88/9;31/3:1/2 = 62/3😉 = 62/3

Откуда номер направляющей строки r = 3 (индекс минимального значения).

Итерация №3.

Базисные переменные:

<X> = (3, 5, 6)

Выбираем столбцы под номерами(3, 5, 6) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (0, 41/3, 0, -22/3, 0, -4)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(3,5,6) = (0, 0, -4)

cN(1,2,4) = (0, 41/3, -22/3, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (11/3, 0, -4)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (-8, -11/3, -11/3, 0)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*1,2,4 = cN — uN = (8, 52/3, -11/3, 0)

Откуда номер направляющего столбца s = 3 (индекс максимального по модулю значения из отрицательных элементов).

Выбираем из матрицы А столбец под номером 3.

 

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

Умножаем обратную матрицу B-1 на вектор (a13,…,am3)

a* = B-1 (a13,…,am3)T = (-1/6, 0, 0)T

min(-;31/3:2/3 = 5;62/3:1/3 = 20;) = 5

Откуда номер направляющей строки r = 2 (индекс минимального значения).

Итерация №4.

Базисные переменные:

<X> = (3, 4, 6)

Выбираем столбцы под номерами(3, 4, 6) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (8, 52/3, 0, -11/3, 0, 0)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(3,4,6) = (0, -11/3, 0)

cN(1,2,5) = (8, 52/3, 0, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (11/3, -2, 0)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (6, 62/3, -2, 0)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*1,2,5 = cN — uN = (2, -1, 2, 0)

Откуда номер направляющего столбца s = 2 (индекс максимального по модулю значения из отрицательных элементов).

Выбираем из матрицы А столбец под номером 2.

 

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

Умножаем обратную матрицу B-1 на вектор (a12,…,am2)

a* = B-1 (a12,…,am2)T = (1/2, 0, 0)T

min(71/2:1/2 = 15;-;5:2 = 21/2😉 = 21/2

Откуда номер направляющей строки r = 3 (индекс минимального значения).

Итерация №5.

Базисные переменные:

<X> = (3, 4, 2)

Выбираем столбцы под номерами(3, 4, 2) из матрицы А и формируем матрицу В.

 

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

Матрица c.

c = (2, -1, 0, 0, 2, 0)

Вектор С не содержит отрицательных элементов

Формируем из матрицы С две матрицы: cB — составленная из базисных компонентов вектора С и cN — составленная из небазисных компонентов вектора С.

cB(3,4,2) = (0, 0, -1)

cN(1,5,6) = (2, 2, 0, 0)

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

Матрица N формируется из матрицы А из соответствующих столбцов с номерами N.

 

Вычисляем:

 

Умножаем вектор cB на обратную матрицу B-1. Получаем вектор цен u.

u = cBB-1 = (0, 1/4, -1/2)

Умножаем обратную матрицу B-1 на вектор b.

 

Умножаем вектор u на матрицу N: uN = (-13/4, 1/4, -1/2, 0)

Тогда вектор нулевой строки c* будет равен разности двух векторов cN и uN:

c*1,5,6 = cN — uN = (33/4, 13/4, 1/2, 0)

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

Вектор С не содержит отрицательных элементов. Найдено оптимальное решение X.

Вектор результатов X = (0, 21/2, 61/4)T

Значение целевой функции F(X) = bc = 621/2

 

 

 

 

 

 

Задача 3.

Решить ТЗ, заданную своей таблицей, методом потенциалов. (Слева – мощности поставщиков, сверху – мощности потребителей, в ячейках – тарифы.)

Вариант
задачи, №

Таблица ТЗ

7,

092613 0016 110 Математика 1

Решение.

Математическая модель транспортной задачи:

F = ∑∑cijxij, (1)

при условиях:

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

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

 

1

2

3

4

Запасы

1

5

9

4

6

234

2

7

8

6

9

594

3

1

5

4

2

362

Потребности

347

173

218

452

 

 

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

∑a = 234 + 594 + 362 = 1190

∑b = 347 + 173 + 218 + 452 = 1190

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

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

 

1

2

3

4

Запасы

1

5

9

4

6

234

2

7

8

6

9

594

3

1

5

4

2

362

Потребности

347

173

218

452

 

 

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

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

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

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

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

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

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

x31 = min(362,347) = 347.

x

9

4

6

234

x

8

6

9

594

1

5

4

2

362 — 347 = 15

347 — 347 = 0

173

218

452

0

 

 

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

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

x34 = min(15,452) = 15.

x

9

4

6

234

x

8

6

9

594

1

x

x

2

15 — 15 = 0

0

173

218

452 — 15 = 437

0

 

 

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

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

x13 = min(234,218) = 218.

x

9

4

6

234 — 218 = 16

x

8

x

9

594

1

x

x

2

0

0

173

218 — 218 = 0

437

0

 

 

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

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

x14 = min(16,437) = 16.

x

x

4

6

16 — 16 = 0

x

8

x

9

594

1

x

x

2

0

0

173

0

437 — 16 = 421

0

 

 

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

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

x22 = min(594,173) = 173.

x

x

4

6

0

x

8

x

9

594 — 173 = 421

1

x

x

2

0

0

173 — 173 = 0

0

421

0

 

 

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

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

x24 = min(421,421) = 421.

x

x

<

4

6

0

x

8

x

9

421 — 421 = 0

1

x

x

2

0

0

0

0

421 — 421 = 0

0

 

1

2

3

4

Запасы

1

5

9

4[218]

6[16]

234

2

7

8[173]

6

9[421]

594

3

1[347]

5

4

2[15]

362

Потребности

347

173

218

452

 

 

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

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

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

F(x) = 4*218 + 6*16 + 8*173 + 9*421 + 1*347 + 2*15 = 6518

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

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

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

u1 + v4 = 6; 0 + v4 = 6; v4 = 6

u2 + v4 = 9; 6 + u2 = 9; u2 = 3

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

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

u3 + v1 = 1; -4 + v1 = 1; v1 = 5

 

v1=5

v2=5

v3=4

v4=6

u1=0

5

9

4[218]

6[16]

u2=3

7

8[173]

6

9[421]

u3=-4

1[347]

5

4

2[15]

 

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

(2;1): 3 + 5 > 7; ∆21 = 3 + 5 — 7 = 1

(2;3): 3 + 4 > 6; ∆23 = 3 + 4 — 6 = 1

max(1,1) = 1

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

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

 

1

2

3

4

Запасы

1

5

9

4[218]

6[16]

234

2

7[+]

8[173]

6

9[421][-]

594

3

1[347][-]

5

4

2[15][+]

362

Потребности

347

173

218

452

 

 

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

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

 

1

2

3

4

Запасы

1

5

9

4[218]

6[16]

234

2

7[347]

8[173]

6

9[74]

594

3

1

5

4

2[362]

362

Потребности

347

173

218

452

 

 

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

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

u1 + v4 = 6; 0 + v4 = 6; v4 = 6

u2 + v4 = 9; 6 + u2 = 9; u2 = 3

u2 + v1 = 7; 3 + v1 = 7; v1 = 4

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

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

 

v1=4

v2=5

v3=4

v4=6

u1=0

5

9

4[218]

6[16]

u2=3

7[347]

8[173]

6

9[74]

u3=-4

1

5

4

2[362]

 

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

(2;3): 3 + 4 > 6; ∆23 = 3 + 4 — 6 = 1

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

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

 

1

2

3

4

Запасы

1

5

9

4[218][-]

6[16][+]

234

2

7[347]

8[173]

6[+]

9[74][-]

594

3

1

5

4

2[362]

362

Потребности

347

173

218

452

 

 

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

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

 

1

2

3

4

Запасы

1

5

9

4[144]

6[90]

234

2

7[347]

8[173]

6[74]

9

594

3

1

5

4

2[362]

362

Потребности

347

173

218

452

 

 

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

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

u2 + v3 = 6; 4 + u2 = 6; u2 = 2

u2 + v1 = 7; 2 + v1 = 7; v1 = 5

u2 + v2 = 8; 2 + v2 = 8; v2 = 6

u1 + v4 = 6; 0 + v4 = 6; v4 = 6

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

 

v1=5

v2=6

v3=4

v4=6

u1=0

5

9

4[144]

6[90]

u2=2

7[347]

8[173]

6[74]

9

u3=-4

1

5

4

2[362]

 

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

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

F(x) = 4*144 + 6*90 + 7*347 + 8*173 + 6*74 + 2*362 = 6097

 

 

 

 

 

 

 

 

Задача 4.

Предприятие (игрок A) планирует выпуск продукции на квартал, рассматривая несколько различных вариантов своей деятельности (стратегии A 1, A 2, …). Конкурирующее предприятие (игрок B) может выбрать различные варианты поведения на рынке (стратегии B 1, B 2, …). Прогнозируемая прибыль предприятия A за квартал в зависимости от сложившейся ситуации задаётся платёжной матрицей, определяющей соответствующую матричную игру (МИ). Требуется:

1) рассмотреть статистическую игру, заданную исходной платёжной матрицей, и определить оптимальные стратегии игрока A в соответствии с критерием Вальда, критерием Гурвица с показателем пессимизма γ, критерием Сэвиджа и критерием Лапласа.

2) вычислить нижнюю и верхнюю цену игры, найти гарантирующие стратегии игроков A и B;

3) упростить платёжную матрицу путём отбрасывания доминируемых стратегий игроков A и B;

4) найти оптимальную смешанную стратегию игрока A и цену игры графическим методом;

5) для определения оптимальной смешанной стратегии игрока B составить стандартную задачу ЛП, решить её симплекс-методом, найти оптимальную смешанную стратегию и вычислить цену игры.

 

Вариант
задачи, №

Платёжная матрица

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

5.

092613 0016 111 Математика 1

0,8

Решение.

Критерий Байеса.

По критерию Байеса за оптимальные принимается та стратегия (чистая) Ai, при которой максимизируется средний выигрыш a или минимизируется средний риск r.

Считаем значения ∑(aijpj)

∑(a1,jpj) = 3•0.25 + (-4)•0.25 + 4•0.25 + 4•0.25 = 1.75

∑(a2,jpj) = 0•0.25 + 2•0.25 + 3•0.25 + 1•0.25 = 1.5

∑(a3,jpj) = (-1)•0.25 + 1•0.25 + 2•0.25 + 0•0.25 = 0.5

∑(a4,jpj) = (-2)•0.25 + 0•0.25 + 1•0.25 + (-1)•0.25 = -0.5

∑(a5,jpj) = 2•0.25 + (-5)•0.25 + 3•0.25 + 1•0.25 = 0.25

Ai

П1

П2

П3

П4

∑(aijpj)

A1

0.75

-1

1

1

1.75

A2

0

0.5

0.75

0.25

1.5

A3

-0.25

0.25

0.5

0

0.5

A4

-0.5

0

0.25

-0.25

-0.5

A5

0.5

-1.25

0.75

0.25

0.25

pj

0.25

0.25

0.25

0.25

0

Выбираем из (1.75; 1.5; 0.5; -0.5; 0.25) максимальный элемент max=1.75

Вывод: выбираем стратегию N=1.

Критерий Лапласа.

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

q1 = q2 = … = qn = 1/n.

qi = 1/4

Ai

П1

П2

П3

П4

∑(aij)

A1

0.75

-1

1

1

1.75

A2

0

0.5

0.75

0.25

1.5

A3

-0.25

0.25

0.5

0

0.5

A4

-0.5

0

0.25

-0.25

-0.5

A5

0.5

-1.25

0.75

0.25

0.25

pj

0.25

0.25

0.25

0.25

0

 

Выбираем из (1.75; 1.5; 0.5; -0.5; 0.25) максимальный элемент max=1.75

Вывод: выбираем стратегию N=1.

Критерий Вальда.

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

a = max(min aij)

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

 

Ai

П1

П2

П3

П4

min(aij)

A1

3

-4

4

4

-4

A2

0

2

3

1

0

A3

-1

1

2

0

-1

A4

-2

0

1

-1

-2

A5

2

-5

3

1

-5

 

Выбираем из (-4; 0; -1; -2; -5) максимальный элемент max=0

Вывод: выбираем стратегию N=2.

Критерий Севиджа.

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

a = min(max rij)

Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.

Находим матрицу рисков.

Риск – мера несоответствия между разными возможными результатами принятия определенных стратегий. Максимальный выигрыш в j-м столбце bj = max(aij) характеризует благоприятность состояния природы.

1. Расчитываем 1-й столбец матрицы рисков.

r11 = 3 — 3 = 0; r21 = 3 — 0 = 3; r31 = 3 — (-1) = 4; r41 = 3 — (-2) = 5; r51 = 3 — 2 = 1;

2. Расчитываем 2-й столбец матрицы рисков.

r12 = 2 — (-4) = 6; r22 = 2 — 2 = 0; r32 = 2 — 1 = 1; r42 = 2 — 0 = 2; r52 = 2 — (-5) = 7;

3. Расчитываем 3-й столбец матрицы рисков.

r13 = 4 — 4 = 0; r23 = 4 — 3 = 1; r33 = 4 — 2 = 2; r43 = 4 — 1 = 3; r53 = 4 — 3 = 1;

4. Расчитываем 4-й столбец матрицы рисков.

r14 = 4 — 4 = 0; r24 = 4 — 1 = 3; r34 = 4 — 0 = 4; r44 = 4 — (-1) = 5; r54 = 4 — 1 = 3;

Ai

П1

П2

П3

П4

A1

0

6

0

0

A2

3

0

1

3

A3

4

1

2

4

A4

5

2

3

5

A5

1

7

1

3

 

Результаты вычислений оформим в виде таблицы.

Ai

П1

П2

П3

П4

max(aij)

A1

0

6

0

0

6

A2

3

0

1

3

3

A3

4

1

2

4

4

A4

5

2

3

5

5

A5

1

7

1

3

7

 

Выбираем из (6; 3; 4; 5; 7) минимальный элемент min=3

Вывод: выбираем стратегию N=2.

Критерий Гурвица.

Критерий Гурвица является критерием пессимизма — оптимизма. За (оптимальную принимается та стратегия, для которой выполняется соотношение:

max(si)

где si = y min(aij) + (1-y)max(aij)

При y = 1 получим критерий Вальде, при y = 0 получим – оптимистический критерий (максимакс).

Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Рассчитываем si.

s1 = 0.8•(-4)+(1-0.8)•4 = -2.4

s2 = 0.8•0+(1-0.8)•3 = 0.6

s3 = 0.8•(-1)+(1-0.8)•2 = -0.4

s4 = 0.8•(-2)+(1-0.8)•1 = -1.4

s5 = 0.8•(-5)+(1-0.8)•3 = -3.4

Ai

П1

П2

П3

П4

min(aij)

max(aij)

y min(aij) + (1-y)max(aij)

A1

3

-4

4

4

-4

4

-2.4

A2

0

2

3

1

0

3

0.6

A3

-1

1

2

0

-1

2

-0.4

A4

-2

0

1

-1

-2

1

-1.4

A5

2

-5

3

1

-5

3

-3.4

 

Выбираем из (-2.4; 0.6; -0.4; -1.4; -3.4) максимальный элемент max=0.6

Вывод: выбираем стратегию N=2.

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

 

Задача 5.

Задан взвешенный граф. Требуется найти кратчайший путь из вершины I в вершину S методом динамического программирования на графе.

Вариант
задачи, №

Структура графа

10.

092613 0016 112 Математика 1

Решение.

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

Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных (если таковые имеются). Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

алгоритм маршрут оптимальный вершина

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

Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.

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

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

Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.

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

В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.

Начнем строить дерево со стороны точки S. В этой вершине есть четыре пути, длиной 4,8,9 и 7. Итак, выбираем путь длиной 4. Попадаем в точку №7. Оттуда идет снова два пути, длиной 9 и 5. Снова выбираем минимальную длину – 5. Попадаем в точку №4. Оттуда в точку №1 есть только два пути: прямой, длиной 7 и через №3 длиной 9+2. Выбираем прямой (кратчайший путь) – длиной 7.

Тогда минимальный путь из точки I в точку S будет: 1-4-7-10, общей длиной 7+5+4=16.

Ответ: минимальный путь из точки I в точку S будет: 1-4-7-10, общей длиной 7+5+4=16

 

<

Комментирование закрыто.

WordPress: 22.95MB | MySQL:124 | 4,319sec