Определение и построение оптимального опорного плана

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

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

.

Решение

Построим область допустимых решений. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Построим уравнение x₁-9x₂ = 16 по двум точкам. Для нахождения первой точки приравниваем x₁ = -2. Находим x₂ = -2. Для нахождения второй точки приравниваем x₂ = -1. Находим x₁ = 7. Соединяем точку (-2;-2) с (7;-1) прямой линией. Построим уравнение 2x₁+4x₂ = 1 по двум точкам. Для нахождения первой точки приравниваем x₁ = -1. Находим x₂ = 0.75. Для нахождения второй точки приравниваем x₁ = 4. Находим x₂ = -7/4. Соединяем точку (-1;0.75) с (4;-7/4) прямой линией. Построим уравнение 7x₁+3x₂ = 27 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 9. Для нахождения второй точки приравниваем x₂ = -2. Находим x₁ =33/7. Соединяем точку (0;9) с (-2;33/7) прямой линией.

Построим область допустимых значений:



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

2. Предприятию необходимо перевезти со склада по железной дороге продукцию трех видов: продукции первого вида не более c₁ изделий, продукции второго вида не более c₂ изделий и продукции третьего вида не более c₃ изделий. Для этой перевозки подразделение железной дороги может выделить специально оборудованные вагоны двух типов А и В. Для полной загрузки вагона в него следует помещать продукцию всех трех видов. При этом в вагон типа А входят a₁ изделий первого вида, a₂ изделий второго вида и a₃ изделий третьего вида. В вагон типа В входят b₁ изделий первого вида, b₂ изделий второго вида и b₃ изделий третьего вида. Экономия от перевозки в вагоне типа А составляет руб., в вагоне типа В - руб.

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

Найти решение двумя способами: геометрически и симплекс методом.

a₁ = 6, b₁ = 3, c₁ = 714, = 3, a₂ = 5, b₂ = 10, c₂ = 910, = 9. a₃ = 3, b₃ = 12, c₃ = 948.

Решение

Построим математическую модель:

Пусть х₁ - количество вагонов 1го типа, х₂ - количество вагонов 2го типа.

Тогда количество продукции первого вида составит .

Тогда количество продукции второго вида составит .

Тогда количество продукции третьего вида составит .

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

Математическая модель имеет вид:

,

.

Решим задачу графически:

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

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

А:

B:

Максимальное значение достигается функцией в точке А, и равно .

Найдем решение с помощью симплекс-метода.

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

В 1-м неравенстве вводим базисную переменную x₃. Во 2-м неравенстве смысла базисную переменную x₄. В 3-м неравенстве вводим базисную переменную x₅.

,

.

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

,

Первый опорный план: Х=(0,0,714,910,948). Опорный план не оптимален, т.к. в целевой функции коэффициенты при F(x) положительные. При x₂ коэффициент максимальный. Поэтому будем выражать переменную х₂.

Найдем D=min{238,91,79}=79.

Переменную х₂ выразим из третьего уравнения.

После преобразований получим систему:

,

Второй опорный план: Х=(0,79,477,120,0). Опорный план не оптимален, т.к. в целевой функции коэффициенты при F(x) положительные. При x₁ коэффициент максимальный. Поэтому будем выражать переменную х₁.

Найдем D=min{636/7,48,316}=48.

Переменную х₁ выразим из третьего уравнения.

После преобразований получим систему:

,

Х=(48,67).

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

F(X) = 3*48 + 9*67 = 747

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

3. Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1, А2 и А3 находится груз в количестве соответственно а1, а2 и а3 т. В пункты В1, В2, В₃, В₄ и В₅ требуется доставить соответственно b₁, b₂, b₃, b₄ и b₅ т груза. Расстояния между пунктами поставки и пунктами потребления приведены в следующей таблице.

Таблица 1

Пункты поставки	Пункты потребления
	В1	В2	В3	В4	В5
А1	d11	d12	d13	d14	d15
А2	d21	d22	d23	d24	d25
А3	d31	d32	d33	d34	d35

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

а₁ = 150, b₂ = 70, а₂ = 150, b₃ = 130, а₃ = 200, b₄ = 110, b₁ = 100, b₅ = 90.

Решение

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3	9	15	35
150	14	10	12	20	46
200	25	11	16	19	48

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

= 150 + 150 + 200 = 500

= 100 + 70 + 130 + 110 + 90 = 500

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

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

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

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

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

Получим опорный план:

Таблица 2

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [70]	9 [80]	15	35
150	14 [100]	10	12 [50]	20	46
200	25	11	16	19 [110]	48 [90]

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

Строим новый план.

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

F(x) = 3*70 + 9*80 + 14*100 + 12*50 + 19*110 + 48*90 = 9340

Начнем строить с элемента 9. Получим опорный план:

Таблица 3

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20]	9 [130]	15	35
150	14 [100]	10 [50]	12	20	46
200	25	11	16	19 [110]	48 [90]

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

Строим новый план.

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

F(x) = 3*20 + 9*130 + 14*100 + 10*50 + 19*110 + 48*90 = 9540

Начнем строить с элемента 10.

Таблица 4

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3	9 [130]	15 [20]	35
150	14 [80]	10 [70]	12	20	46
200	25 [20]	11	16	19 [90]	48 [90]

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

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

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

F(x) = 9*130 + 15*20 + 14*80 + 10*70 + 25*20 + 19*90 + 48*90 = 9820

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 9; 0 + v₃ = 9; v₃ = 9

u₁ + v₄ = 15; 0 + v₄ = 15; v₄ = 15

u₃ + v₄ = 19; 15 + u₃ = 19; u₃ = 4

u₃ + v₁ = 25; 4 + v₁ = 25; v₁ = 21

u₂ + v₁ = 14; 21 + u₂ = 14; u₂ = -7

u₂ + v₂ = 10; -7 + v₂ = 10; v₂ = 17

u₃ + v₅ = 48; 4 + v₅ = 48; v₅ = 44

Таблица 5

	v1=21	v2=17	v3=9	v4=15	v5=44
u1=0	20	3	9[130]	15[20]	35
u2=-7	14[80]	10[70]	12	20	46
u3=4	25[20]	11	16	19[90]	48[90]

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

(1;1): 0 + 21 > 20; ?₁₁ = 0 + 21 - 20 = 1

(1;2): 0 + 17 > 3; ?₁₂ = 0 + 17 - 3 = 14

(1;5): 0 + 44 > 35; ?₁₅ = 0 + 44 - 35 = 9

(3;2): 4 + 17 > 11; ?₃₂ = 4 + 17 - 11 = 10

Max (1,14,9,10) = 14

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

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

Таблица 6

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [+]	9 [130]	15 [20] [-]	35
150	14 [80] [+]	10 [70] [-]	12	20	46
200	25 [20] [-]	11	16	19 [90] [+]	48 [90]

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

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

Таблица 7

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20]	9 [130]	15	35
150	14 [100]	10 [50]	12	20	46
200	25 [0]	11	16	19 [110]	48 [90]

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₂ + v₂ = 10; 3 + u₂ = 10; u₂ = 7

u₂ + v₁ = 14; 7 + v₁ = 14; v₁ = 7

u₃ + v₁ = 25; 7 + u₃ = 25; u₃ = 18

u₃ + v₄ = 19; 18 + v₄ = 19; v₄ = 1

u₃ + v₅ = 48; 18 + v₅ = 48; v₅ = 30

u₁ + v₃ = 9; 0 + v₃ = 9; v₃ = 9

Таблица 8

	v1=7	v2=3	v3=9	v4=1	v5=30
u1=0	20	3[20]	9[130]	15	35
u2=7	14[100]	10[50]	12	20	46
u3=18	25[0]	11	16	19[110]	48[90]

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

(2;3): 7 + 9 > 12; ?₂₃ = 7 + 9 - 12 = 4

(3;2): 18 + 3 > 11; ?₃₂ = 18 + 3 - 11 = 10

(3;3): 18 + 9 > 16; ?₃₃ = 18 + 9 - 16 = 11

max(4,10,11) = 11

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

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

Таблица 9

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20] [+]	9 [130] [-]	15	35
150	14 [100] [+]	10 [50] [-]	12	20	46
200	25 [0] [-]	11	16 [+]	19 [110]	48 [90]

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

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

Таблица 10

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20]	9 [130]	15	35
150	14 [100]	10 [50]	12	20	46
200	25	11	16 [0]	19 [110]	48 [90]

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₂ + v₂ = 10; 3 + u₂ = 10; u₂ = 7

u₂ + v₁ = 14; 7 + v₁ = 14; v₁ = 7

u₁ + v₃ = 9; 0 + v₃ = 9; v₃ = 9

u₃ + v₃ = 16; 9 + u₃ = 16; u₃ = 7

u₃ + v₄ = 19; 7 + v₄ = 19; v₄ = 12

u₃ + v₅ = 48; 7 + v₅ = 48; v₅ = 41

Таблица 11

	v1=7	v2=3	v3=9	v4=12	v5=41
u1=0	20	3[20]	9[130]	15	35
u2=7	14[100]	10[50]	12	20	46
u3=7	25	11	16[0]	19[110]	48[90]

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

(1;5): 0 + 41 > 35; ?₁₅ = 0 + 41 - 35 = 6

(2;3): 7 + 9 > 12; ?₂₃ = 7 + 9 - 12 = 4

(2;5): 7 + 41 > 46; ?₂₅ = 7 + 41 - 46 = 2

max(6,4,2) = 6

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

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

Таблица 12

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20]	9 [130] [-]	15	35 [+]
150	14 [100]	10 [50]	12	20	46
200	25	11	16 [0] [+]	19 [110]	48 [90] [-]

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

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

Таблица 13

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20]	9 [40]	15	35 [90]
150	14 [100]	10 [50]	12	20	46
200	25	11	16 [90]	19 [110]	48

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₂ + v₂ = 10; 3 + u₂ = 10; u₂ = 7

u₂ + v₁ = 14; 7 + v₁ = 14; v₁ = 7

u₁ + v₃ = 9; 0 + v₃ = 9; v₃ = 9

u₃ + v₃ = 16; 9 + u₃ = 16; u₃ = 7

u₃ + v₄ = 19; 7 + v₄ = 19; v₄ = 12

u₁ + v₅ = 35; 0 + v₅ = 35; v₅ = 35

Таблица 14

	v1=7	v2=3	v3=9	v4=12	v5=35
u1=0	20	3[20]	9[40]	15	35[90]
u2=7	14[100]	10[50]	12	20	46
u3=7	25	11	16[90]	19[110]	48

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

(2;3): 7 + 9 > 12; ?₂₃ = 7 + 9 - 12 = 4

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

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

Таблица 15

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [20] [+]	9 [40] [-]	15	35 [90]
150	14 [100]	10 [50] [-]	12 [+]	20	46
200	25	11	16 [90]	19 [110]	48

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

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

Таблица 16

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [60]	9	15 [20]	35 [90]
150	14 [100]	10 [10]	12 [40]	20	46
200	25	11	16 [90]	19 [110]	48

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₂ + v₂ = 10; 3 + u₂ = 10; u₂ = 7

u₂ + v₁ = 14; 7 + v₁ = 14; v₁ = 7

u₂ + v₃ = 12; 7 + v₃ = 12; v₃ = 5

u₃ + v₃ = 16; 5 + u₃ = 16; u₃ = 11

u₃ + v₄ = 19; 11 + v₄ = 19; v₄ = 8

u₁ + v₅ = 35; 0 + v₅ = 35; v₅ = 35

Таблица 17

	v1=7	v2=3	v3=5	v4=8	v5=35
u1=0	20	3[60]	9	15	35[90]
u2=7	14[100]	10[10]	12[40]	20	46
u3=11	25	11	16[90]	19[110]	48

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

(3;2): 11 + 3 > 11; ?₃₂ = 11 + 3 - 11 = 3

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

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

Таблица 18

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [60]	9	15	35 [90]
150	14 [100]	10 [10] [-]	12 [40] [+]	20	46
200	25	11 [+]	16 [90] [-]	19 [110]	48

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

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

Таблица 19

Пункты поставки	Пункты потребления
	100	70	130	110	90
150	20	3 [60]	9	15	35 [90]
150	14 [100]	10	12 [50]	20	46
200	25	11 [10]	16 [80]	19 [110]	48

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₃ + v₂ = 11; 3 + u₃ = 11; u₃ = 8

u₃ + v₃ = 16; 8 + v₃ = 16; v₃ = 8

u₂ + v₃ = 12; 8 + u₂ = 12; u₂ = 4

u₂ + v₁ = 14; 4 + v₁ = 14; v₁ = 10

u₃ + v₄ = 19; 8 + v₄ = 19; v₄ = 11

u₁ + v₅ = 35; 0 + v₅ = 35; v₅ = 35

Таблица 20

	v1=10	v2=3	v3=8	v4=11	v5=35
u1=0	20	3[60]	9	15	35[90]
u2=4	14[100]	10	12[50]	20	46
u3=8	25	11[10]	16[80]	19[110]	48

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

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

F(x) = 3*60 + 35*90 + 14*100 + 12*50 + 11*10 + 16*80 + 19*110 = 8810

4. Найти наибольшее и наименьшее значения функции в заданной области графическим методом. Применить метод множителей Лагранжа для поиска наименьшего значения этой функции.

Построим функцию Лагранжа:

Дополнительные условия:

Условие стационарности

Условие дополняющей нежёсткости



Рассмотрим различные варианты значений :

а) Если

а1) Если

Если

Если , то

Если , то

Если то

Если , то

Тогда и , возникает противоречие.

Если

Если , то х₁=0, х₂=1

Если , то х₂=0, х₁=1.

а2) Если

Если

Если

Если

Решая систему получим решение х₁=4,5, х₂=1,5.

Если

,

,

Если

Если



Если

Решая систему найдем х₂=-6, х₁=7

б) Если

б1) Если

Если

Если

Если , то

Решая систему получим х₁=5,6 и х₂=1,2.

Если то и х₁=8.

Если тогда х₁=0 и х₂=4

Если

Если

Если , то

Х₂=7, х₁=-6.

Если , то

Подставив

Если , то

Подставив :

б2) Если



Если

Если , то

Если , то и подставив

Если

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

Найдем значение функции в найденных точках:

Для точки =0. Не входит в ОДЗ.

Для точки =36. Входит в ОДЗ.

Для точки =29. Входит в ОДЗ.

Для точки =2,5. Входит в ОДЗ.

Для точки =5. Входит в ОДЗ.

Для точки =205. Не входит в ОДЗ.

Для точки =169. Входит в ОДЗ.

Для точки =65. Входит в ОДЗ.

Для точки =0,8. Не входит в ОДЗ.

Для точки =16. Не входит в ОДЗ.

Для точки =2,6. Не входит в ОДЗ.

Для точки =40. Не входит в ОДЗ.

Среди найденных значений найдем максимальное и минимальное.

В точке =169 - максимальное значение.

В точке =2,5. - минимальное значение.

Решим задачу графически:

=

Данная функция графически представляет собой окружность с центром в точке (6,2) и радиусом равным С.

От величины С зависти радиус окружности. При увеличении значения С радиус окружности увеличивается. При уменьшении значения С окружность меняется.

Построим несколько окружностей с разными радиусами:

Построим ограничения на графике:



В точке функция =169 принимает максимальное значение.

В точке =2,5. - минимальное значение.

Построим искомые окружности с минимальным и максимальным значением функции:

5. Определить нижнюю и верхнюю цену игры, найти оптимальное решение и цену игры, заданной матрицей.

Проверим, имеет ли платежная матрица седловую точку.

- нижняя цена игры.

- верхняя цена игры.

Следовательно, седловой точки нет (т.к. ).

Тогда, цена игры находится в перделах 4 ? С ? 6.

Находим решение игры в смешанных стратегиях.

Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ? a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ? a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

Находим решение игры в смешанных стратегиях.

Решим задачу графически:

p₁ -вероятность выбора игроком А 1-ой стратегии.

p₂ -вероятность выбора игрока А 2-ой стратегии.

q₁ -вероятность выбора игроком B 1-ой стратеги.

q₂ -вероятность выбора игроком B 2-ой стратегии.

Средний выигрыш игрока А при выборе игроком В стратегии В₁ равен С=6p₁+3(1-p₁), Средний выигрыш игрока А при выборе игроком В стратегии В₂ равен С=4p₁+8(1-p₁).

Построим огибающую:



Найдем С (точка пересечения прямых):

,

C=

Средний выигрыш игрока B при выборе игроком A стратегии A₁ равен С=6q₁+4(1-q₁), Средний выигрыш игрока B при выборе игроком A стратегии A₂ равен С=3q₁+8(1-q₁).

Построим огибающую:

Найдем С (точка пересечения прямых):

C=

6. Предприятие может оказывать транспортные услуги трех видов А₁, А₂, А₃, получая при этом прибыль, зависящую от спроса, который может находиться в одном из четырех состояний В₁, В₂, В₃, В₄.

Таблица 1

Виды услуг	Возможные состояния спроса
	В1	В2	В3	В4
А1	a11	a12	a13	a14
А2	a21	a22	a23	a24
А3	a31	a32	a33	a34

Элементы матрицы характеризуют величину прибыли a_ij, которую получит предприятие, если будет оказывать i-й вид транспортных услуг при j-м состоянии спроса на эти услуги.

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

Таблица 2

Виды услуг	Возможные состояния спроса
	В1	В2	В3	В4
А1	5	3	7	6
А2	6	8	5	9
А3	9	6	0	4

Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Таблица 3

Игроки	B1	B2	B3	B4	а = min(Ai)
A1	5	3	7	6	3
A2	6	8	5	9	5
A3	9	6	0	4	0
b = max(Bi)	9	8	7	9

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 5, которая указывает на максимальную чистую стратегию A₂.

Верхняя цена игры b = min(b_j) = 7.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 5 ? С ? 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ? a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ? a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

Находим решение игры в смешанных стратегиях.

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

найти минимум функции F(x) при ограничениях:

5x₁+6x₂+9x₃ ? 1

3x₁+8x₂+6x₃ ? 1

7x₁+5x₂ ? 1

6x₁+9x₂+4x₃ ? 1

F(x) = x₁+x₂+x₃ > min

неравенство план оптимальность симплекс

найти максимум функции G(y) при ограничениях:

5y₁+3y₂+7y₃+6y₄ ? 1

6y₁+8y₂+5y₃+9y₄ ? 1

9y₁+6y₂+4y₄ ? 1

G(y) = y₁+y₂+y₃+y₄ > max

Решаем эти системы симплексным методом.

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

Приведем систему ограничений к системе неравенств смысла ?, умножив соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = x₁ + x₂ + x₃ при следующих условиях-ограничениях.

- 5x₁ - 6x₂ - 9x₃?-1

- 3x₁ - 8x₂ - 6x₃?-1

- 7x₁ - 5x₂?-1

- 6x₁ - 9x₂ - 4x₃?-1

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

В 1-м неравенстве смысла (?) вводим базисную переменную x₄. В 2-м неравенстве смысла (?) вводим базисную переменную x₅. В 3-м неравенстве смысла (?) вводим базисную переменную x₆. В 4-м неравенстве смысла (?) вводим базисную переменную x₇.

-5x₁-6x₂-9x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ = -1

-3x₁-8x₂-6x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ = -1

-7x₁-5x₂ + 0x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ = -1

-6x₁-9x₂-4x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ = -1

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

Таблица 4

-5	-6	-9	1	0	0	0
-3	-8	-6	0	1	0	0
-7	-5	0	0	0	1	0
-6	-9	-4	0	0	0	1

Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆, x₇,

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

X1 = (0,0,0,-1,-1,-1,-1)

Таблица 5

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	-1	-5	-6	-9	1	0	0	0
x5	-1	-3	-8	-6	0	1	0	0
x6	-1	-7	-5	0	0	0	1	0
x7	-1	-6	-9	-4	0	0	0	1
F(X0)	0	-1	-1	-1	0	0	0	0

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

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

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

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 1-ая строка, а переменную x₄ следует вывести из базиса.

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

Минимальное значение ? соответствует 3-му столбцу, т.е. переменную x₃ необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-9).

Таблица 6

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	-1	-5	-6	-9	1	0	0	0
x5	-1	-3	-8	-6	0	1	0	0
x6	-1	-7	-5	0	0	0	1	0
x7	-1	-6	-9	-4	0	0	0	1
F(X0)	0	-1	-1	-1	0	0	0	0

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

Таблица 7

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

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

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

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

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 3-ая строка, а переменную x₆ следует вывести из базиса.

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

Минимальное значение ? соответствует 1-му столбцу, т.е. переменную x₁ необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-7).

Таблица 8

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	1/9	5/9	2/3	1	-1/9	0	0	0
x5	-1/3	1/3	-4	0	-2/3	1	0	0
x6	-1	-7	-5	0	0	0	1	0
x7	-5/9	-37/9	-61/3	0	-4/9	0	0	1
F(X0)	1/9	-4/9	-1/3	0	-1/9	0	0	0
?	0	-4/9 : (-7) = 4/63	-1/3 : (-5) = 1/15	-	-	-	-	-

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

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

Таблица 9

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	2/63	0	17/63	1	-1/9	0	5/63	0
x5	-8/21	0	-45/21	0	-2/3	1	1/21	0
x1	1/7	1	5/7	0	0	0	-1/7	0
x7	-1/63	0	-340/63	0	-4/9	0	-34/63	1
F(X1)	11/63	0	-1/63	0	-1/9	0	-4/63	0

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

План 2 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

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

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 2-ая строка, а переменную x₅ следует вывести из базиса.

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

Минимальное значение ? соответствует 2-му столбцу, т.е. переменную x₂ необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-4⁵/₂₁).

Таблица 10

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	2/63	0	17/63	1	-1/9	0	5/63	0
x5	-8/21	0	-45/21 ...

Подобные документы

• Определение оптимальных значений вероятности событий

  Решение задачи линейного программирования симплекс-методом. План перевозок при минимальных затратах на них. Определение оптимального значения изменения численности работников. Решение матричной игры двух лиц с применением чистой и смешанной стратегий.
  
  контрольная работа [152,3 K], добавлен 16.05.2013
  

• Исследование операций

  Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
  
  курсовая работа [54,1 K], добавлен 05.03.2010
  

• Применение графического метода и симплекс-метода для решения задач линейного программирования

  Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
  
  контрольная работа [398,2 K], добавлен 15.08.2012
  

• Определение оптимального плана движения морских судов симплекс-методом

  Характеристика направлений перевозок и флота. Расчет нормативов работы судов на схемах движения. Составление математической модели задачи. Нахождение оптимального плана работы флота и оптимальных схем движения судов, построение симплекс таблицы.
  
  курсовая работа [1,4 M], добавлен 24.10.2012
  

• Построение математических моделей линейных систем управления и их моделирование

  Построение асимптотических логарифмических амплитудно- и фазочастотных характеристик. Расчет оптимального плана и экстремального значения функции цели с помощью симплекс-метода. Нахождение экстремума заданной функции с учетом системы ограничений.
  
  курсовая работа [3,2 M], добавлен 25.05.2015
  

• Экономико-математическое моделирование

  Определение нижней и верхней цены игры, заданной платежной матрицей. Имеет ли игра седловую точку? Решение геометрически задачи линейного программирования. Построение графа состояний случайного процесса. Предельные вероятности для заданной системы.
  
  контрольная работа [280,0 K], добавлен 04.02.2011
  

• Математическое программирование

  Вычисление координат экстремумов. Многоугольник решений, вектор нормали и начальная симплекс-таблица. Неотрицательные решения системы неравенств. Оптимизирующая функция и ее минимум. Разница потенциалов, условие оптимальности и система потенциалов.
  
  контрольная работа [754,3 K], добавлен 11.05.2009
  

• Оптимизация финансового состояния компании с использованием игровых методов

  Определение чистых стратегий холдинга. Составление платежной матрицы игры, ее верхней и нижней цены. Принятие оптимального решения об инвестиции в банк для получения наибольшей выгоды при улучшении финансового состояния металлургическому консорциуму.
  
  курсовая работа [85,3 K], добавлен 19.05.2014
  

• Построение оптимального плана перевозок груза с минимальной стоимостью

  Определение первичного опорного плана разными способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Перепланировка поставок с помощью метода потенциалов для каждого плана. Анализ эффективности их использования.
  
  контрольная работа [67,2 K], добавлен 06.11.2012
  

• Составление оптимального плана производства дополнительной продукции с использованием симплекс-метода

  Линейное программирование как инструмент исследования линейных моделей. Основы симплекс-метода. Моделирование экономической ситуации в инструментальном цехе. Применение симплекс-метода для оптимизации плана производства. Применимость линейной модели.
  
  курсовая работа [112,0 K], добавлен 09.12.2014
  

• Экономико-математическое моделирование объектов отрасли

  Расчет количества изделий для изготовления на предприятии, чтобы прибыль от их реализации была максимальной (решение графическим способом и в среде MS Excel). Определение равновесной цены спроса-предложения на товар, нижней и верхней цены матричной игры.
  
  контрольная работа [352,0 K], добавлен 13.09.2013
  

• Линейное программирование и методы оптимизации

  Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
  
  задача [579,8 K], добавлен 11.07.2010
  

• Методы принятия управленческих решений для перевозки грузов из пунктов отправления в пункты потребления

  Определение транспортных задач закрытого и открытого типов. Построение опорных планов методом северо-западного угла, минимальной стоимости и методом Фогеля. Анализ оптимального плана по перевозке груза. Достижение минимума затрат и времени на перевозку.
  
  курсовая работа [6,2 M], добавлен 05.11.2014
  

• Разработка оптимального плана поставок

  Системы массового обслуживания и параметры, характеризующие эффективность их функционирования. Классификация СМО и их основные элементы. Построение модели плана поставок и нахождение опорного решения. Оптимизация задачи методом отрицательных циклов.
  
  курсовая работа [53,8 K], добавлен 01.09.2011
  

• Оптимизация плана производства

  Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
  
  курсовая работа [458,6 K], добавлен 10.12.2013
  

• Методы принятия управленческих решений

  Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
  
  контрольная работа [613,3 K], добавлен 18.02.2014
  

• Математические методы в экономике

  Определение оптимального числа контролеров-кассиров в магазине, при котором суммарные потери фирмы будут минимальными. Составление плана заказов на товары для обеспечения оптимального соотношения между их продажей. Построение сетевого графика продаж.
  
  контрольная работа [126,2 K], добавлен 16.01.2012
  

• Сетевая модель строительного предприятия "СтройКам"

  Таблица событий по возведению двухэтажного офиса строительным предприятием "СтройКам". Особенности разработки оптимального плана, максимально сокращающего длительность осуществления проекта при минимальных затратах, методом математического моделирования.
  
  курсовая работа [103,0 K], добавлен 06.08.2013
  

• Транспортная задача

  Определение минимального значения целевой функции. Проведение проверки плана на оптимальность. Определение значения оценок для всех свободных клеток транспортной задачи, признака оптимальности. Введение перевозки, выявление цикла, перемещение по циклу.
  
  задача [64,1 K], добавлен 20.05.2015
  

• Запись математической модели в форме стандартной задачи линейного программирования

  Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
  
  дипломная работа [311,3 K], добавлен 17.01.2014
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам