ММЭ_вар9

ЗАДАНИЕ 1

Решить задачу линейного программирования графическим способом и с помощью инструмента «Поиск решения» табличного процессора MS Excel.

Решение:

1. Графический способ.

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

x2=(8-x1)/2

x2=(18-4x1)/4

x2=1+x1

х2=2

Луч АВ прямой x2=2 – это множество допустимых решений.

Построим прямую 3x1+4x2 уровня 12, т.е. прямую 3x1+4x2=12.

Поднимая данную прямую вверх до первого касания с лучом АВ получим точку А – это будет точка минимума. Точка А имеет координаты (4;2), тогда Lmin=L(4;2)=3*4+4*2=20.

Тогда Lmax=∞.

2. С помощью инструмента «Поиск решения» табличного процессора MS Excel.

Заполняем исходные данные:

Оптимальные значения вектора Х=(Х1, Х2) будут помещены в ячейках В3:C3, оптимальное значение целевой функции – в ячейке D4.

1) Заполняем ячейку D4: СУММПРОИЗВ(B$3:C$3;B4:C4). Копируем формулу в ячейки D7:D10.

2) Выбираем: Сервис → Поиск решения; появится диалоговое окно Поиск решения

Заполняем данное окно, как показано ниже.

3) Нажимаем "параметры". Проставляем галочки напротив "линейная модель" и "неотрицательные значения".

Нажимаем OK. Выполнить. Получаем решение задачи.

Итак, имеем Lmin=L(4;2)=20.

Ответ: Lmin=L(4;2)=20.

ЗАДАНИЕ 2

Решить задачу нелинейного программирования графическим способом и с помощью инструмента «Поиск решения» табличного процессора MS Excel.

Решение:

1. Графический способ.

Изобразим множество допустимых значений на координатной плоскости. Отрезок AB прямой x1+x2=6 – это множество допустимых значений.

График целевой функции – эллипс с центром в точке (1;3). Нарисуем эллипс с полуосями, т.е..

Точка, в которой эллипс касается отрезка AB- это решение задачи. Точка касания – (2,2;3,8).

Тогда fmin=f(2,2;3,8)=2*(2,2-1)²+3*(3,8-3)²=4,8

2. С помощью инструмента «Поиск решения» табличного процессора MS Excel.

Заполняем исходные данные:

	A	B	C	D	E	F
1		Переменные
2		X1	X2
3	значения			ЦФ
4
5		Ограничения
6				Левая часть	знак	правая часть
7		1	1		=	6

В нашей задаче оптимальные значения вектора Х=(Х1, Х2) будут помещены в ячейках В3:C3, оптимальное значение целевой функции – в ячейке D4.

1) В ячейке D4 записываем формулу: 2*СТЕПЕНЬ(B3-1;2)+3*СТЕПЕНЬ(C3-3;2)

2) Левая часть ограничений – ячейка D7 – записываем формулу: B7*B3+C7*C3

3) Выбираем: Сервис → Поиск решения; появится диалоговое окно Поиск решения

Заполняем данное окно, как показано ниже.

Получаем решение:

Ответ: fmin=f(2,2;3,8)= 4,8

ЗАДАНИЕ 3

Решить задачу транспортную задачу. Обозначения: Aj – запасы груза в i-м пункте отправления; Bj – потребности в грузе в j-м пункте назначения; Cij – тарифы перевозок единицы груза из i-го пункта отправления в j-м пункт назначения

Решение:

Составим систему ограничений математической модели.

Стоимость перевозки должна быть минимальна:

При условии, что выполняются равенства:

Где Xij – количество единиц продукции, перевозимой от i-го поставщика к j-му потребителю.

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

20+30+40=90; 20+30+20+20=90.

Итак, условие сбалансированности задачи выполняется.

Составим транспортную таблицу:

Поставщики	Потребители				ai	Ui
	B1	B2	B3	B4
А1	4	1	5	3	20	0
	0	20	0	0
А2	2	6	4	7	30	0
	20	0	10	0
А3	5	3	6	4	40	2
	0	10	10	20
bj	20	30	20	20
Vj	2	1	4	2

Будем выбирать первый опорный план согласно методу минимального тарифа.

Минимальный тариф C12=1, тогда X12=min{20;30}=20. Обнуляем первую строку.

Для оставшихся клеток минимальный тариф: С21=2. Тогда X21= min{30;20}=20.

Обнуляем 1-ий столбец.

Далее минимальный тариф С32=3, тогда X32= min{30-20;40}=10. Обнуляем 2-й столбец.

С23=4, Х23= min{30-20;20}=10. Обнуляем 2-ю строку.

С34=4, Х34= min{40-10;20}=20.

Заполним оставшиеся клетки Х33=10.

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

1*20+2*20+4*10+3*10+6*10+4*20=270 д.е.

Количество загруженных клеток равно 6, т.е. равно 3+4-1=6. Таким образом, выполнено условие невырожденности плана.

Проверим план на оптимальность с помощью метода потенциалов. Последовательно из уравнений: Vj=Cij-Ui; Ui=Cij-Vj, составленных для загруженных клеток, определим потенциалы поставщиков и потребителей.

Принимаем U1=0, тогда V2=1-0=1; U3=3-1=2;V3=6-2=4; V4=4-2=2; U2=4-4=0; V1=2-0=2.

Для свободных клеток рассчитаем разности: Δij=Ui+Vj-Cij

Δ11=0+2-4=-2;

Δ13=0+4-5=-1;

Δ14=0+2-3=-1;

Δ22=0+1-6=-5;

Δ24=0+2-7=-5;

Δ31=2+2-5=-1.

Итак, все разности Δij отрицательны, значит, полученный план оптимален. И по этому плану стоимость перевозки составляет 270 д.е.

ЗАДАНИЕ 4

Решить задачу о назначении венгерским методом по известной матрице эффективностей.

Решение:

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

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

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

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

Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 1 и столбце 4 вычеркиваем.

Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем.

Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем.

Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 4 и столбце 1 вычеркиваем.

Фиксируем нулевое значение в клетке (5, 2). Другие нули в строке 5 и столбце 2 вычеркиваем.

Фиксируем нулевое значение в клетке (6, 6). Другие нули в строке 6 и столбце 6 вычеркиваем.

В итоге получаем следующую матрицу:

Количество найденных нулей равно k = 6. В результате получаем эквивалентную матрицу Сэ:

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

Cmin = 2+1+2+1+2+2=10

Альтернативный вариант 2:

Cmin = 2+1+2+1+2+2=10

Альтернативный вариант 3:

Cmin = 2+1+2+2+1+2=10

Итак, минимальная стоимость назначения равна 10.

ЗАДАНИЕ 5

Решить задачу по теме «Элементы теории массового обслуживания».

Вычислите интенсивности потоков λ и μ одноканальной СМО с отказами, если вероятность отказа равна 0,5. а среднее время обслуживания заявки системой – 0,2 суток.

Решение:

Ответ: заявок в сутки; .

ЗАДАНИЕ 6

Найти решение матричных игр.

Решение:

Проверим наличие седловой точки:

-2≠4, значит, игра не имеет седловой точки.

Цена игры находится в пределах от -2 до 4.

Стратегия A₃ доминирует над стратегией A₁ (все элементы строки 3 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Вероятность p₁ = 0.

Получаем матрицу:

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

1. F(x)=x1+x2→min

При ограничениях:

4x1+2x2≥1

5x1-3x2≥1

-2x1+8x2≥1

2. G(y)=y1+y2+y3→max

При ограничениях:

4y1+5y2-2y3≤1

2y1-3у2+8y3≤1

Решим задачу симплекс-методом. Введем дополнительные неотрицательные переменные y4;y5.

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

4y1+5y2-2y3+y4=1

2y1-3у2+8y3+y5=1

Строим симплекс-таблицу.

Базисные переменные	Значения баз. переменных	Значения коэффициентов при переменных					δi
		Y1	Y2	Y3	Y4	Y5
Y4	1	4	5	-2	1	0	1/4
Y5	1	2	-3	8	0	1	1/2
G0	0	-1	-1	-1	0	0
Y1	1/4	1	5/4	-1/2	1/4	0	-
Y5	1/2	0	-5,5	9	-1/2	1	1/18
G1	1/4	0	1/4	-3/2	1/4	0
Y1	5/18	1	17/18	0	2/9	1/18	5/17
Y3	1/18	0	-11/18	1	-1/18	1/9	-
G2	1/3	0	-2/3	0	1/6	1/6
Y2	5/17	18/17	1	0	4/17	1/17
Y3	4/17	11/17	0	1	3/34	5/34
G3	9/17	12/17	0	0	11/34	7/34

Все элементы индексной строки отрицательны, значит, первый опорный план не оптимален.

Возьмем 1-ый столбец за ведущий.

Найдем отношения δi=bi/ai1. Минимальное отношение равно 1/4, тогда 1-ая строка – ведущая. 4-разрешающий элемент.

Делим 1-ую строку на 4, все элементы 1-го столбца кроме 1-го обнуляем.

Таблицу заполняем по правилу прямоугольника.

В индексной строке присутствуют отрицательные элементы. Значит, новый план не оптимален, улучшим его. Третий столбец – ведущий. Вторая строка - ведущая. 9 – разрешающий элемент.

В индексной строке присутствуют отрицательные элементы. Значит, новый план не оптимален, улучшим его. Второй столбец – ведущий. Первая строка – ведущая, 17/18 - разрешающий элемент.

Все элементы индексной строки неотрицательны, значит, план оптимален.

Итак, Gmax=G(0;5/17;4/17)=9/17; Fmin=F(11/34;7/34)=9/17.

Цена игры: g=1/(9/17)=17/9.

Определим стратегии игроков.

1 игрок: p1=0; p2=(11/34)*(17/9)=11/18; p3=(7/34)*(17/9)=7/18.

2 игрок: q1=0*(17/9)=0; q2=(5/17)*(17/9)=5/9; q3=(4/17)*(17/9)=4/9.

Ответ: Цена игры равна 17/9; оптимальная смешанная стратегия первого игрока – (0;11/18;7/18), второго игрока – (0;5/9;4/9).

ЗАДАНИЕ 7.

Решить задачу по теме «Сетевое планирование». Для заданной сетевой модели некоторого комплекса работ определить время и критический путь.

Исходные данные

Показатель
1-2 A 1-4 B 2-4 C 4-6 D 1-5 E 5-4 F 5-7 G 2-3 H 3-6 I 7-6 J 3-8 K 6-8 L 7-8 M	Исследование внутреннего рынка Исследование зарубежного рынка Определение сегмента внутреннего рынка Определение политики освоения сегментов внутреннего и зарубежного рынков Исследование качества выпускаемого товара Разработка программы по адаптации товара на рынке Разработка рекламной политики по продвижению товара на рынке Разработка программы услуг по передвижению товара Выбор посредников Разработка политики оптовой и розничной торговли Разработка торговой марки и упаковки Определение ценовой политики Разработка программы сервисного обслуживания	4 6 5 5 4 6 3 6 5 5 4 7 6

Решение:

Расчёт параметров работ

Код работы (i,j)	Количество предшествующих работ	Продолжительность tij	Раннее начало работ tij^Р.Н.	Раннее окончание работ tij^Р.О.	Поздние сроки начала tij^П.Н.	Поздние сроки окончания tij^П.О.	Резервы времени: полный tij^П	Резервы времени: свободный tij^С.В.	Резервы времени: событий Rj
(1,2)	0	4	0	4	4-4=0	4	0	0	4-4=0
(1,4)	0	6	0	6	10-6=4	10	4	3	10-9=1
(1,5)	0	4	0	4	4-4=0	4	0	0	4-4=0
(2,3)	1	6	4	10	10-6=4	10	0	0	10-10=0
(2,4)	1	5	4	9	10-5=5	10	1	0	10-9=1
(3,6)	1	5	10	15	15-5=10	15	0	0	15-15=0
(3,8)	1	4	10	14	22-4=18	22	8	8	22-22=0
(4,6)	2	5	9	14	15-5=10	15	1	1	15-15=0
(5,4)	1	6	4	10	10-6=4	10	0	-1	10-9=1
(5,7)	1	3	4	7	10-3=7	10	3	0	10-7=3
(6,8)	2	7	15	22	22-7=15	22	0	0	22-22=0
(7,6)	1	5	7	12	15-5=10	15	3	3	15-15=0
(7,8)	1	6	7	13	22-7=15	22	8	8	22-22=0