Математическое програмирование (стр. 3 из 3)

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
	V1 =3	V2=1	V3=1	V4=1	V5=4
А1	U1 =0	9	5	1 20	1 30	9	50
А2	U2=0	7	1 10	4	9	4 20	30
А3	U3=2	5 20	3 20	4 30	9	9	70
Потребности	20	30	50	30	20	150

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

для свободных клеток.

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

Найдем минимальную стоимость перевозок.

Ответ:

Задача 3

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

1) найти решение графическим методом

2) написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.

Решение.

Графическое решение задачи следующее:

Система неравенств определяет область, ограниченную двумя прямыми и координатными осями. График целевой функции представляет собой окружность переменного радиуса с центром в точке (5, 10). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке.

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

Получили точку (3 , 8), значение целевой функции в этой точке равно

Запишем задачу в традиционном виде:

Функция

называется функцией Лагранжа, а переменные - коэффициентами Лагранжа.

Точка

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

Если функции f, gдифференцируемы, то условия определяющие седловую точку (условия Куна-Таккера):

В данном случае получаем:

Подставим в эти выражения значения:

Получаем

Седловая точка функции Лагранжа:

Проверим условие cедловой точки:

Условия выполнены, седловая точка

.

Ответ:

Задача 4

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

, а доход от у единиц, вложенных во второе предприятие равен . Остаток средств к концу года составляет - для первого предприятия, - для второго предприятия. Решить задачу методом динамического программирования.

Решение.

Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

Обозначим

- средства, которые распределяются на k–ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k–ом шаге:

Остаток средств от обоих предприятий на k–ом шаге:

Обозначим

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

Рекуррентные соотношения Беллмана для этих функций

Проведем оптимизацию, начиная с четвертого шага:

4-й шаг.

Оптимальный доход равен:

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

3-й шаг.

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

.

2-й шаг.

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

1-й шаг.

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

.

Результаты оптимизации:

Определим количественное распределение средств по годам:

Так как

, , получаем

Представим распределение средств в виде таблицы:

предприятие	год
	1	2	3	4
1	900	90	9	0,9
2	0	0	0	0

При таком распределении средств за 4 года будет получен доход, равный

Ответ: