Referat.me / Математика / Математическое програмирование

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

Вид работы: реферат

Размер файла: 736.29 Kb

Скачать файл: referat.me-214688.docx

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

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

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

Задача 1

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

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

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

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

Решение.

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

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

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

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

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

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

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

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

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

Базис	C_б	В	2	3	0	0	0
Базис	C_б	В	А₁	А₂	А₃	А₄	А₅
А₃	0	48	2	2	1	0	0
А₄	0	38	1	2	0	1	0
А₅	0	54	3	1	0	0	1
F_i - C_i	0	-2	-3	0	0	0

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

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

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

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

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

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

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

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

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

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

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

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

Базис	C_б	В	2	3	0	0	0
Базис	C_б	В	А₁	А₂	А₃	А₄	А₅
А₃	0	10	1	0	1	-	0
А₅	0	19	0,5	1	0	0,5	0
А₂	3	35	2,5	0	0	-0,5	1
F_i - C_i	57	-0,5	0	0	1,5	0

Таким образом, новыми базисными переменными становятся А₃ , А₅ , А₂ .

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

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

Вычисляем:

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

Новыми базисными переменными становятся A₅ , A₂ , A₁

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

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

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

Базис	C_б	В	2	3	0	0	0
Базис	C_б	В	А₁	А₂	А₃	А₄	А₅
А₅	0	10	1	0	1	-1	0
А₂	3	14	0	1	-0,5	1	0
А₁	2	10	0	0	-2,5	2	1
F_i - C_i	62	0	0	1,5	1	0,5

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

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

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

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

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

Задача 2

Имеются три пункта отправления А₁ ,А₂ ,А₃ однородного груза и пять пунктов В₁ , В₂ , В₃ , В₄ , В₅ его назначения. На пунктах А₁ ,А₂ ,А₃ находится груз в количествах 50, 30, 70 тонн. В пункты В₁ , В₂ , В₃ , В₄ , В₅ требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:

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

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

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

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

Решение.

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

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

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

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

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

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

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

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

Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =9	V₂ =5	V₃ =4	V₄ =9	V₅ =9
А₁	U₁ =0	9 20	5 30	1	1	9	50
А₂	U₂ =0	7	1	4 30	9	4	30
А₃	U₃ =0	5	3	4 20	9 30	9 20	70
Потребности	20	30	50	30	20	150

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

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

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =9	V₂ =5	V₃ =4	V₄ =9	V₅ =9
А₁	U₁ =0	9	5 30	1	1 20	9	50
А₂	U₂ =0	7	1	4 30	9	4	30
А₃	U₃ =0	5 20	3	4 20	9 10	9 20	70
Потребности	20	30	50	30	20	150

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

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

Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =5	V₂ =5	V₃ =4	V₄ =1	V₅ =9
А₁	U₁ =0	9	5 30	1	1 20	9	50
А₂	U₂ =0	7	1	4 30	9	4	30
А₃	U₃ =0	5 20	3	4 20	9 10	9 20	70
Потребности	20	30	50	30	20	150

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

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

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =5	V₂ =5	V₃ =4	V₄ =1	V₅ =9
А₁	U₁ =0	9	5 10	1 20	1 20	9	50
А₂	U₂ =0	7	1	4 10	9	4 20	30
А₃	U₃ =0	5 20	3 20	4 20	9 10	9	70
Потребности	20	30	50	30	20	150

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

Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =2	V₂ =5	V₃ =1	V₄ =1	V₅ =1
А₁	U₁ =0	9	5 10	1 20	1 20	9	50
А₂	U₂ =3	7	1	4 10	9	4 20	30
А₃	U₃ =3	5 20	3 20	4 20	9 10	9	70
Потребности	20	30	50	30	20	150

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

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

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =2	V₂ =5	V₃ =1	V₄ =1	V₅ =1
А₁	U₁ =0	9	5	1 20	1 30	9	50
А₂	U₂ =3	7	1 10	4	9	4 20	30
А₃	U₃ =3	5 20	3 20	4 30	9	9	70
Потребности	20	30	50	30	20	150

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

Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

Пункты отправления	Пункты назначения					Запасы
	В₁	В₂	В₃	В₄	В₅	Запасы
	V₁ =3	V₂ =1	V₃ =1	V₄ =1	V₅ =4
А₁	U₁ =0	9	5	1 20	1 30	9	50
А₂	U₂ =0	7	1 10	4	9	4 20	30
А₃	U₃ =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 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен , а доход от у единиц, вложенных во второе предприятие равен . Остаток средств к концу года составляет - для первого предприятия, - для второго предприятия. Решить задачу методом динамического программирования.