Составить математическую модель и решить задачу симплексным методом.
В производстве пользующихся спросом двух изделий (A и B) принимают участие 3 цеха фирмы. На изготовление одного изделия А 1-й цех затрачивает 10 ч, 2-й цех – 9 ч, 3-й цех – 3 ч. На изготовление одного изделия В 1-й цех затрачивает 18 ч, 2-й цех – 15 ч, 3-й цех – 1 ч. На производство обоих изделий 1-й цех может затратить не более 1238 ч, 2-й цех – не более 1118 ч, 3-й цех – не более 523 ч.
От реализации одного изделия А фирма получает доход 11 рублей, изделия В – 13 рублей.
Определить максимальный доход от реализации всех изделий А и В.
Решение
Математическая модель задачи
Переменные задачи:
x1 – количество изделий А, ед;
x2 – количество изделий В, ед.
Тогда:
10x1+18x2 – время, затраченное первым цехом, ч;
9x1+15x2 – время, затраченное вторым цехом, ч;
3x1+x2 – время, затраченное третьим цехом, ч.
Ограничения:
На производство обоих изделий 1-й цех может затратить не более 1238 ч, 2-й цех – не более 1118 ч, 3-й цех – не более 523 ч:
10x1+18x2 ≤1238(1)
9x1+15x2≤1118(2)
3x1+x2 ≤523(3)
По смыслу задачи переменные должны быть неотрицательными целыми числами:
xi≥0,xi-целое , i=1,2(4)
Целевая функция:
От реализации одного изделия А фирма получает доход 11 рублей, изделия В – 13 рублей, тогда общая прибыль равна:
F=11x1+13x2(5)
Таким образом, получена математическая модель задачи:
Найти максимальное значение функции F=11x1+13x2→max при условиях:
10x1+18x2 ≤12389x1+15x2≤11183x1+x2 ≤523xi≥0,xi-целое i=1,2
Решение задачи симплекс-методом
Запишем задачу в форме основной задачи линейного программирования. В системе ограничений перейдем от неравенств к равенствам, для чего введем дополнительные переменные x3,x4, x5 ≥0.
Система ограничений примет вид:
10x1+18x2+x3=12389x1+15x2+x4=11183x1+x2+x5=523xi≥0, i=1,5xi-целое,i=1,2
Целевая функция примет вид:
FX=11x1+13x2+0∙x3+0∙x4+0∙x5→max
Преобразованную систему ограничений можно записать в векторной форме:
x1Р1+x2Р2+x3Р3+x4Р4+x5Р5=Р0, где
Р1=1093, Р2=18151, Р3=100, Р4=010, Р5=001, Р0=12381118523
Для основной задачи можно записать опорный план X1=(0;0;1238;1118;523), который определяется системой единичных векторов Р3, Р4, Р5 (они образуют базис трехмерного пространства).
Составим первую симплекс-таблицу.
Таблица 1
№ Базис Сб
Р0
Переменные
11 13 0 0 0
1 x3
0 1238 10 18 1 0 0
2 x4
0 1118 9 15 0 1 0
3 x5
0 523 3 1 0 0 1
F=0 –11 –13 0 0 0
Опорный план: X1=(0;0;1238;1118;523).
F=0∙1238+0∙1118+0∙523=0
Найдем оценки:
∆j=i=13ciaij-cj
где cj – коэффициенты при неизвестных целевой функции,
aij – коэффициенты при неизвестных в системе ограничений, ci – коэффициенты при базисных переменных.
Оценки в столбцах базисных переменных равны 0: ∆3=∆4=∆5=0.
∆1=0∙10+0∙9+0∙3-11=-11
∆2=0∙18+0∙15+0∙1-13=-13
Поскольку среди есть отрицательные оценки, то опорный план не является оптимальным. Среди коэффициентов при переменных в соответствующих столбцах есть положительные, поэтому можно перейти к новому базису и другому опорному плану.
В качестве переменной, вводимой в базис, возьмем переменную x2 (отрицательная оценка по модулю максимальна)
. Столбец переменной x2 – ключевой.
Для определения переменной, подлежащей исключению из базиса, составим отношения элементов столбца Р0 к соответствующим положительным значениям ключевого столбца и найдем среди них минимальное:
min123818; 111815;5231=123818
Значит, из базиса выводим переменную x3. Первая строка – ключевая, a12=18 – разрешающий элемент.
Перейдем ко второй симплекс-таблице.
Таблица 2
№ Базис Сб
Р0
Переменные
11 13 0 0 0
1 x2
13 6879
59
1 118
0 0
2 x4
0 8613
23
0 -56
1 0
3 x5
0 45429
249
0 -118
0 1
F=89419
-379
0 1318
0 0
Заполнение второй симплекс-таблицы:
В столбцах переменных, входящих в базис, на пересечении строк и столбцов одноименных переменных проставляются 1, а остальные элементы этих столбцов равны 0.
Элементы столбцов Р0 и в строке переменной, вводимой в базис, получаем делением соответствующих элементов исходной таблицы на разрешающий элемент.
Остальные элементы столбцов Р0 и находим по правилу треугольника. Для вычисления какого-либо из этих элементов берем 3 числа:
число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;
число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего переменной, вводимой в базис;
число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и ключевой строки.
Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают произведение второго и третьего.
столбец Р0 1118-15∙6879=8613
523-1∙6879=45429
Х1 9-15∙59=23
3-1∙59=249
Х3 0-15∙118=-56
0-1∙118=-118
Опорный план: X2=(0;6879;0;8613;45429).
F=13∙6879+0∙8613+0∙45429=89419
Найдем оценки:
Оценки в столбцах базисных переменных равны 0: ∆2=∆4=∆5=0.
∆1=13∙59+0∙23+0∙49-11=-379
∆3=13∙118+0∙-56+0∙-118-0=1318
Поскольку среди есть отрицательные оценки, то опорный план не является оптимальным. Среди коэффициентов при переменных в соответствующих столбцах есть положительные, поэтому можно перейти к новому базису и другому опорному плану.
В качестве переменной, вводимой в базис, берем переменную x1 (единственная отрицательная оценка)
Задать вопрос
на новый заказ в Автор24.
