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

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

Задача 1

Для производства двух видов изделий А и В используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2 часа, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час.

На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 48 часа, оборудование второго типа – 38 часов, оборудование третьего типа – 54 часов.

Прибыль от реализации единицы готового изделия А составляет 2 денежные единицы, а изделия В – 3 денежные единицы.

Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.

Решение.

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

Прибыль рассчитывается по формуле:

Запишем математическую модель задачи:

Решим данную задачу графически.

Для этого построим на плоскости области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.

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

График целевой функции передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (10 ; 14). В этой точке целевая функция будет достигать максимума.

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

Составляем симплекс-таблицу:

Базис	Cб	В	2	3	0	0	0
			А1	А2	А3	А4	А5
А3	0	48	2	2	1	0	0
А4	0	38	1	2	0	1	0
А5	0	54	3	1	0	0	1
Fi - Ci	0	-2	-3	0	0	0

В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – А3
, А4
, А5
. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.

В следующий столбец записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi
при i –й переменной.

Под столбцом свободных членов записывается начальная оценка

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

Преобразуем симплекс-таблицу следующим образом:

Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.

Шаг 2: Для отрицательных оценок вычисляются величины:

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

Шаг 3: Вторая строка таблицы делится на 2

От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.

От элементов строки 3 отнимает соответствующие элементы строки 2.

От элементов строки 4 отнимает соответствующие элементы строки 2, умноженные на -3.

Базис	Cб	В	2	3	0	0	0
			А1	А2	А3	А4	А5
А3	0	10	1	0	1	-	0
А5	0	19	0,5	1	0	0,5	0
А2	3	35	2,5	0	0	-0,5	1
Fi - Ci	57	-0,5	0	0	1,5	0

Таким образом, новыми базисными переменными становятся А3
, А5
, А2
.

Возвращаемся к шагу 1 и повторяем весь процесс.

Проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А1
.

Вычисляем:

Разрешающим элементом будет первый элемент первого столбца – 1.

Новыми базисными переменными становятся A5
, A2
, A1

От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 0,5.

От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 2,5.

От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -0,5.

Базис	Cб	В	2	3	0	0	0
			А1	А2	А3	А4	А5
А5	0	10	1	0	1	-1	0
А2	3	14	0	1	-0,5	1	0
А1	2	10	0	0	-2,5	2	1
Fi - Ci	62	0	0	1,5	1	0,5

Отрицательных оценок нет, то есть критерий оптимальности выполнен.

Таким образом, получается искомое значение целевой функции

F(10; 14; 0; 0; 10) = 62, т.е. возвращаясь к системе неравенств, получаем:

Ответы, полученные различными методами, совпадают.

Ответ: хопт
= ( 10 , 14) Значение функции : F = 62

Задача 2

Имеются три пункта отправления А1
,А2
,А3
однородного груза и пять пунктов В1
, В2
, В3
, В4
, В5
его назначения. На пунктах А1
,А2
,А3
находится груз в количествах 50, 30, 70 тонн. В пункты В1
, В2
, В3
, В4
, В5
требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:

Пункты отправления	Пункты назначения
	В1	В2	В3	В4	В5
А1	9	5	1	1	9
А2	7	1	4	9	4
А3	5	3	4	9	9

Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.

Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах;

2) для решения задачи использовать методы северо-западного угла и потенциалов.

Решение.

Составим математическую модель задачи:

Обозначим - количество груза, перевезенного из пункта отправления i в пункт назначения j.

Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):

При этом должна быть минимизирована целевая функция

Построим опорный план методом северо-западного угла:

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	9 20	5 30	1	1	9	50
А2	7	1	4 30	9	4	30
А3	5	3	4 20	9 30	9 20	70
Потребности	20	30	50	30	20	150

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

Построим систему потенциалов. Ui
- потенциалы, соответствующие поставщикам, Vi
- потенциалы, соответствующие потребителям.

Полагаем U1
=0, а далее Ui
+ Vi
= dij
для занятых клеток таблицы.

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

Проверим критерий оптимальности : для свободных клеток.

Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (1 , 4). Перебросим в ячейку (1 , 4) 20 единиц груза из ячейки (1 , 1).

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

Чтобы компенсировать недостаток в третьей строке, перебросим те же 20 единиц груза из ячейки (3 , 4) в ячейку (3 , 1).

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

Полагаем U1
=0, а далее Ui
+ Vi
= dij
для занятых клеток таблицы.

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

Проверим критерий оптимальности : для свободных клеток.

Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2 , 5). Перебросим в ячейку (2 ,5) 20 единиц груза из ячейки (1 , 2).

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

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

Полагаем U1
=0, а далее Ui
+ Vi
= dij
для занятых клеток таблицы.

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

Проверим критерий оптимальности : для свободных клеток.

Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2 , 2). Перебросим в ячейку (2 ,2) 10 единиц груза из ячейки (1 , 2).

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

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

Полагаем U1
=0, а далее Ui
+ Vi
= dij
для занятых клеток таблицы.

Пункты отправления	Пункты назначения					Запасы
	В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 года будет получен доход, равный

Ответ: