Задачи математического программирования (стр. 5 из 6)

Для заданной математической постановки задачи НП (целевой функции f(x) и ограничений - равенств) выполнить следующие действия:

Найти все условные экстремумы функций методом множителей Лагранжа и выбрать среди них глобальный минимум (максимум);

Проверить результаты решения в табличном процессоре Excel;

(1)

Метод множителей Лагранжа

Необходимо перевести условие к виду

Составим вспомогательную функцию Лагранжа:

Для данной задачи получим:

(2)

Дифференцируем данную функцию по х1, х2, x3,

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

(3)

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

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

х1=2,25, х2=-1,25, x3= 1,5,

=-1,5 и =-3, F=12

Точка экстремума заданной функции f(x) - (х1, х2, x3), является точкой глобального минимума при заданных ограничениях функции.

Решение в табличном процессоре Excel. Проверим результаты решения в табличном процессоре Excel.

Решение задачи с помощью процессора Excel дало следующие результаты:

Таблица 13

х1	х2	x3
2,25	-1,25	1,50
Целевая функция	12,00
Ограничения	4,00	=	4
6,00	=	6

Решения задачи обеими методами дали одинаковый результат.

Лабораторная работа №5 (задача динамического программирования об оптимальном распределении инвестиций)

Задача

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

Таблица 14

X	g1	g2	g3	g4
0	0	0	0	0
20	14	17	22	20
40	26	20	21	33
60	35	32	37	46
80	52	61	67	30
100	61	72	58	42

Решение

Этап I. Условная оптимизация.

Шаг 1. k = 4. Предполагаем, что все средства 100 ден.ед. переданы на инвестирование четвертого предприятия. В этом случае максимальная прибыль составит F4(C4)= 46, данные представлены в таблице 15.

Таблица 15.

C4	x4						F4(C4)	X*
	0	20	40	60	80	100
0	0	-	-	-	-	-	0	0
20	-	20	-	-	-	-	20	20
40	-	-	33	-	-	-	33	40
60	-	-	-	46	-	-	46	60
80	-	-	-	-	30	-	30	80
100	-	-	-	-	-	42	42	100

Шаг 2. k = 3. Определяем оптимальную стратегию инвестирования в третье и четвертое предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:

.

На его основании рассчитываются данные таблицы 16

Таблица 16.

C3	X3						F3(C3)	X*
	0	20	40	60	80	100
0	0+0	-	-	-	-	-	0	0
20	0+20	22+0	-	-	-	-	22	20
40	0+33	22+20	21+0	-	-	-	42	20
60	0+46	22+33	21+20	37+0	-	-	55	20
80	0+30	22+46	21+33	37+20	67+0	-	68	20
100	0+42	22+30	21+46	37+33	67+20	58+0	87	20

Шаг 3. k = 2. Определяем оптимальную стратегию инвестирования во второе и третье предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:

.

На его основании рассчитываются данные таблицы 3.

Таблица 17.

C2	X2						F2(C2)	X*
	0	20	40	60	80	100
0	0+0	-	-	-	-	-	0	0
20	0+22	17+0	-	-	-	-	22	0
40	0+42	17+22	20+0	-	-	-	42	0
60	0+55	17+42	20+22	32+0	-	-	59	20
80	0+68	17+55	20+42	32+22	61+0	-	72	20
100	0+87	17+68	20+55	32+42	61+22	72+0	87	0

Шаг 4. k = 1. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:

.

На его основе находятся данные таблицы 4.

Таблица 18.

C1	X1						F1(C1)	X*
	0	20	40	60	80	100
0	0+0	-	-	-	-	-	0	0
20	0+48	14+0	-	-	-	-	22	0
40	0+93	14+48	26+0	-	-	-	42	0
60	0+135	14+93	26+48	35+0	-	-	59	0
80	0+149	14+135	26+93	35+48	52+0	-	72	0
100	0+160	14+149	26+135	35+93	52+48	61+0	87	0

По данным последней таблицы максимальных доход с четырех предприятий составил 87 д.ед. При этом первое и второе предприятия не принесут никакого дохода, в них нецелесообразно вкладывать инвестиции. В 3-е предприятие нужно вложить 80 д.ед. В 4-е предприятие нужно вложить 20 д.ед. В итоге останется 20-Получается, что оптимальный план Х*(0;0;80;20)

Лабораторная работа №5 (задача динамического программирования о выборе оптимального пути в транспортной сети)

Задача

В предложенной из начального пункта (1) в конечный пункт (11). Стоимость проезда между отдельными пунктами транспортной сети придумать самостоятельно и транспортной сети имеется несколько маршрутов по проезду представить в соответствующей таблице (T(i,j)). Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.

Рисунок 2 – Транспортная сеть

Элементы матрицы маршрутов транспортной сети, а так же стоимость проезда из пункта i в пункт j (tij) представлена в таблице 19.

Таблица 19.

ji	1	2	3	4	5	6	7	8	9	10	11
1	-	10	12	8	20	-	-	-	-	-	-
2	-	-	-	-	-	15	11	-	-	-	-
3	-	-	-	-	-	6	9	-	-	-	-
4	-	-	-	-	-	7	10	-	-	-	-
5	-	-	-	-	-	13	8	-	-	-	-
6	-	-	-	-	-	-	-	12	14	18	-
7	-	-	-	-	-	-	-	13	15	16	-
8	-	-	-	-	-	-	-	-	-	-	8
9	-	-	-	-	-	-	-	-	-	-	10
10	-	-	-	-	-	-	-	-	-	-	10
11	-	-	-	-	-	-	-	-	-	-	-