Разработка оптимального плана производства
Предприятие выпускает два типа изделий A и B, для производства которых используется сырье трех типов S1, S2, S3. На изготовление единицы изделия А необходимо затратить сырья каждого вида в количестве 6, 5 и 3 ед. соответственно, а на изготовление изделия В затрачивают 3, 10, 12 единиц сырья. Производство обеспечено сырьем каждого вида в количестве 714, 910, 948 единиц соответственно, выпускаемая продукция реализуется по цене 3 ден. ед. за единицу изделия А и 9 ден. ед. за единицу изделия В. Составить план производства изделий А и В, обеспечивающий максимум выпускаемой продукции (в денежном выражении) при заданных ограничениях на ресурсы (запасы сырья):
1) решить задачу линейного программирования симплексным методом;
2) дать геометрическую интерпретацию решения;
3) сформулировать задачу, двойственную к исходной задаче, и найти ее оптимальное решение.
Решение
1. Решим задачу линейного программирования симплексным методом.
Целевая функция:
F(X) = 3x1 + 9x2 → max
Условия-ограничения.
6x1 + 3x2 ≤ 714
5x1 + 10x2 ≤ 910
3x1 + 12x2 ≤ 948
x1, x2 > 0
Чтобы построить первый опорный план, систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме):
6x1 + 3x2 + x3 = 714
5x1 + 10x2 + x4 = 910
3x1 + 12x2 + x5 = 948
Решим систему уравнений относительно базисных переменных x3, x4, x5
Принимая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0, 0, 714, 910, 948)
Базис B x1
x2
x3
x4
x5
x3
714 6 3 1 0 0
x4
910 5 10 0 1 0
x5
948 3 12 0 0 1
F(X0) 0 -3 -9 0 0 0
Итерация №0.
Текущий опорный план неоптимален, поскольку в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, т. к. это наибольший коэффициент по модулю. Определим значения Di по строкам как частное от деления bi / ai2 и из них выберем наименьшее: min (714 : 3 , 910 : 10 , 948 : 12 ) = 79. То есть, 3-я строка является ведущей. Разрешающий элемент равен 12 и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1
x2
x3
x4
x5
min
x3
714 6 3 1 0 0 238
x4
910 5 10 0 1 0 91
x5
948 3 12 0 0 1 79
F(X1) 0 -3 -9 0 0 0
Вместо переменной x5 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент (РЭ), равный 12. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ:
НЭ = СЭ – (А × В) / РЭ
где СЭ – элемент старого плана, РЭ – разрешающий элемент, А и В – элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Расчет каждого элемента представлен в таблице:
B x1
x2
x3
x4
x5
714 – (948 × 3) : 12 6 – (3 × 3) : 12 3 – (12 × 3) : 12 1 – (0 × 3) : 12 0 – (0 × 3) : 12 0 – (1 × 3) : 12
910 – (948 × 10) : 12 5 – (3 × 10) : 12 10 – (12 × 10) : 12 0 – (0 × 10) : 12 1 – (0 × 10) : 12 0 – (1 × 10) : 12
948 : 12 3 : 12 12 : 12 0 : 12 0 : 12 1 : 12
0 – (948 × -9) : 12 -3 – (3 × -9) : 12 -9 – (12 × -9) : 12 0 – (0 × -9) : 12 0 – (0 × -9) : 12 0 – (1 × -9) : 12
Новая симплекс-таблица:
Базис B x1
x2
x3
x4
x5
x3
477 5,25 0 1 0 -0,25
x4
120 2,5 0 0 1 -0,833
x2
79 0,25 1 0 0 0,083
F(X1) 711 -0,75 0 0 0 0,75
Текущий опорный план неоптимален, т. к. в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1, т. к. это наибольший коэффициент по модулю. Определим значения Di по строкам как частное от деления bi / ai1 и из них выберем наименьшее: min (477 : 5.25 , 120 : 2.5 , 79 : 0.25 ) = 48
. То есть 2-я строка является ведущей. Разрешающий элемент равен 2,5 и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1
x2
x3
x4
x5
min
x3
477 5,25 0 1 0 -0,25 90,857
x4
120 2,5 0 0 1 -0,833 48
x2
79 0,25 1 0 0 0,083 316
F(X2) 711 -0,75 0 0 0 0,75
Вместо переменной x4 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на РЭ = 2,5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Расчет каждого элемента:
B x1
x2
x3
x4
x5
477 – (120 × 5,25) : 2,5 5,25 – (2,5 × 5,25) : 2,5 0 – (0 × 5,25) : 2,5 1 – (0 × 5,25) : 2,5 0 – (1 × 5,25) : 2,5 -0,25 – (-0,833 × 5,25) : 2,5
120 : 2,5 2,5 : 2,5 0 : 2,5 0 : 2,5 1 : 2,5 -0,833 : 2,5
79 – (120 × 0,25) : 2,5 0,25 – (2,5 × 0,25) : 2,5 1 – (0 × 0,25) : 2,5 0 – (0 × 0,25) : 2,5 0 – (1 × 0,25) : 2,5 0,083 – (-0,833 × 0,25) : 2,5
711 – (120 × -0,75) : 2,5 -0,75 – (2,5 × -0,75) : 2,5 0 – (0 × -0,75) : 2,5 0 – (0 × -0,75) : 2,5 0 – (1 × -0,75) : 2,5 0,75 – (-0,833 × -0,75) : 2,5
Новая симплекс-таблица:
Базис B x1
x2
x3
x4
x5
x3
225 0 0 1 -2,1 1,5
x1
48 1 0 0 0,4 -0,333
x2
67 0 1 0 -0,1 0,167
F(X2) 747 0 0 0 0,3 0,5
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис B x1
x2
x3
x4
x5
x3
225 0 0 1 -2,1 1,5
x1
48 1 0 0 0,4 -0,333
x2
67 0 1 0 -0,1 0,167
F(X3) 747 0 0 0 0,3 0,5
Оптимальный план:
x1 = 48, x2 = 67
F(X) = 3 × 48 + 9 × 67 = 747
Выводы:
В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 225.
Значение 0 в столбце x1 означает, что использование x1 выгодно.
Значение 0 в столбце x2 означает, что использование x2 выгодно.
Значение 0 в столбце x3 означает, что теневая цена (двойственная оценка) равна y1 = 0.
Значение 0,3 в столбце x4 означает, что теневая цена (двойственная оценка) равна y2 = 0,3.
Значение 0,5 в столбце x5 означает, что теневая цена (двойственная оценка) равна y3 = 0,5.
2. Геометрическая интерпретация решения. Используем приведенные выше критерии.
Целевая функция:
F(X) = 3x1 + 9x2 → max
Условия-ограничения.
6x1 + 3x2 ≤ 714 (1)
5x1 + 10x2 ≤ 910 (2)
3x1 + 12x2 ≤ 948 (3)
x1, x2 > 0
Построим область допустимых решений, т. е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости (обозначены штрихом), заданные неравенствами.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Построим прямую, отвечающую значению функции F = 3x1 + 9x2 = 0
Задать вопрос
на новый заказ в Автор24.
