Линейное программирование и теория двойственности
Для изготовления двух видов продукции используется три вида сырья. При производстве единицы продукции первого вида затрачивается 5 кг сырья первого вида, 3 кг сырья второго вида и 2 кг сырья третьего вида. При производстве единицы продукции второго вида затрачивается 2 кг сырья первого вида, 3 кг сырья второго вида и 3 кг сырья третьего вида. Запасы сырья первого вида составляют 505 кг, второго – 393, третьего – 348 кг. Прибыль от реализации единицы продукции первого вида составляет 7 руб., а прибыль от реализации единицы продукции второго вида 4 руб. Построить экономико-математическую модель задачи, максимизирующую прибыль от реализации продукции. Решить задачу геометрически. Построить двойственную задачу и найти ее решение на основе теорем двойственности. Провести содержательный экономический анализ полученных результатов.
Решение
Пусть необходимо изготовить продукции 1 – х1, продукции 2 – х2, тогда ограничения
по сырью 1:5x1+2x2≤505,по сырью 2:3x1+3x2≤393,по сырью 3:2x1+3x2≤348,
по неотрицательности переменных:
x1 ≥ 0,x2 ≥ 0.
Прибыль определяется как F=7x1+4x2, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F = 7x1+4x2 → max5x1+2x2≤505,3x1+3x2≤393,2x1+3x2≤348,x1 ≥ 0,x2 ≥ 0.
Необходимо найти максимальное значение целевой функции F = 7x1+4x2 при системе ограничений:
5x1+2x2≤505, (1)3x1+3x2≤393, (2)2x1+3x2≤348, (3)x1 ≥ 0, (4)x2 ≥ 0. (5)Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
Построим уравнение 5x1+2x2 = 505 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 252.5. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 101. Соединяем точку (0;252.5) с (101;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:5 ∙ 0 + 2 ∙ 0 - 505 ≤ 0, т.е. 5x1+2x2 - 505≤ 0 в полуплоскости ниже прямой.
Построим уравнение 3x1+3x2 = 393 по двум точкам. Для нахождения первой точки приравниваем x1 = 0
. Находим x2 = 131. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 131. Соединяем точку (0;131) с (131;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:3 ∙ 0 + 3 ∙ 0 - 393 ≤ 0, т.е. 3x1+3x2 - 393≤ 0 в полуплоскости ниже прямой.
Построим уравнение 2x1+3x2 = 348 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 116. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 174. Соединяем точку (0;116) с (174;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:2 ∙ 0 + 3 ∙ 0 - 348 ≤ 0, т.е. 2x1+3x2 - 348≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 7x1+4x2 → max.
Построим прямую, отвечающую значению функции F = 7x1+4x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (7;4)
Задать вопрос
на новый заказ в Автор24.
