Завод ремонтирует тракторы двух типов

Математическая модель задачи
Введем обозначения:
x1 – количество тракторов 1 типа, которые надо отремонтировать;
x2 – количество тракторов 2 типа, которые надо отремонтировать.
Тогда прибыль от ремонта тракторов равна (млн. руб.):
1∙x1+2∙x2
Ограничения:
За месяц завод может отремонтировать не более 150 тракторов, т.е. должно выполняться условие:
x1+x2≤150
Завод должен получить прибыль не менее 240 млн. руб., т.е. должно выполняться условие:
x1+2x2≥240
Тракторов 1 типа необходимо отремонтировать не менее 50 штук:
x1≥50
По смыслу задачи количество тракторов не может быть дробным или отрицательным числом:
x1≥0, x2≥0,; x1,x2-целое
Целевая функция: общая мощность отремонтированных тракторов (л.с.), должна быть максимальной:
W=300∙x1+200∙x2
Получаем математическую модель задачи: найти максимальное значение целевой функции
W=300x1+200x2→max
(1)
при ограничениях:
x1+x2≤150x1+2x2≥240x1≥50x1≥0, x2≥0x1,x2-целое
(2)
Решение задачи симплекс-методом
Запишем задачу в форме основной задачи линейного программирования. В системе ограничений перейдем от неравенств к равенствам, для чего введем дополнительные переменные x3,x4, x5 ≥0.
Система ограничений примет вид:
x1+x2+x3=150x1+2x2-x4=240x1-x5=50xi≥0, i=1,5x1,x2-целое
Целевая функция примет вид:
W=300x1+200x2+0∙x3+0∙x4+0∙x5→max
Преобразованную систему ограничений можно записать в векторной форме:
x1Р1+x2Р2+x3Р3+x4Р4+x5Р5=Р0, где
Р1=111, Р2=120, Р3=100, Р4=0-10, Р5=00-1, Р0=15024050
Так как среди векторов Pi, i=1,5 нет трех единичных векторов, которые можно было бы взять в качестве базиса, то будем решать задачу методом искусственного базиса (М-метод).
Перейдем к расширенной задаче. Введем дополнительные переменные x6,x7 ≥0, M>0 – достаточно большое число.
Система ограничений примет вид:
x1+x2+x3=150x1+2x2-x4+x6=240x1-x5+x7=50xi≥0, i=1,7x1,x2-целое (1*)
Целевая функция примет вид:
W=300x1+200x2+0∙x3+0∙x4+0∙x5-M∙x6-M∙x7→max(2*)
Преобразованную систему ограничений можно записать в векторной форме:
x1Р1+x2Р2+x3Р3+x4Р4+x5Р5+x6Р6+x7Р7=Р0, где
Р1=111, Р2=120, Р3=100, Р4=0-10, Р5=00-1, Р6=010, Р7=001 Р0=15024050
Для расширенной задачи можно записать опорный план X=(0;0;150;0;0;240;50), который определяется системой единичных векторов Р3, Р6, Р7 (они образуют базис).
Составим первую симплекс-таблицу.
Таблица 1
№ Базис Сб
Р0
Переменные
x6
x7
300 200 0 0 0 -М -М
1 Р3
0 150 1 1 1 0 0 0 0
2 Р6
-М 240 1 2 0 -1 0 1 0
3 Р7
-М 50 1 0 0 0 -1 0 1
М
Z= -290 -2 -2 0 1 1 0 0
0 -300 -200 0 0 0 0 0
Опорный план: X=(0;0;150;0;0;240;50).
Найдем оценки:
∆j=i=13ciaij-cj
где cj – коэффициенты при неизвестных целевой функции (2*)
aij – коэффициенты при неизвестных в системе ограничений, ci – коэффициенты при базисных переменных.
∆1=0-М-М-300=-2М-300
∆2=0-2М-0-200=-2М-200
∆3=0+0+0-0=0
∆4=0+М+0-0=М
∆5=0+0+М-0=М
∆6=0-М+0+М=0
∆6=0+0-М+М=0
W=0-240М-50М=-290М
Поскольку среди есть отрицательные оценки (ориентируемся на строку М), то опорный план не является оптимальным . Среди коэффициентов при переменных в соответствующих столбцах есть положительные, поэтому можно перейти к новому базису и другому опорному плану.
В качестве переменной, вводимой в базис, возьмем переменную x1. Столбец переменной x4 – ключевой.
Для определения переменной, подлежащей исключению из базиса, составим отношения элементов столбца Р0 к соответствующим положительным значениям ключевого столбца и найдем среди них минимальное:
min1501; 2401;501=501
Значит, из базиса выводим переменную x7. Поскольку это искусственная переменная, то в дальнейшем ее нет смысла вводить в базис, и столбец этой переменной в новой симплекс-таблице нет смысла вычислять.
Третья строка – ключевая, a71=1 – разрешающий элемент.
Перейдем ко второй симплекс-таблице.
Таблица 2
№ Базис Сб
Р0
Переменные
x6
x7
300 200 0 0 0 -М
1 Р3
0 100 0 1 1 0 1 0
2 Р6
-М 190 0 2 0 -1 1 1
3 Р1
300 50 1 0 0 0 -1 0
М
Z= -190 0 -2 0 1 -1 0
15000 0 -200 0 0 -300 0
Заполнение второй симплекс-таблицы:
В столбцах переменных, входящих в базис, на пересечении строк и столбцов одноименных переменных проставляются 1, а остальные элементы этих столбцов равны 0.
Элементы столбцов Р0 и в строке переменной, вводимой в базис, получаем делением соответствующих элементов исходной таблицы на разрешающий элемент.
Остальные элементы столбцов Р0 и находим по правилу треугольника. Для вычисления какого-либо из этих элементов берем 3 числа:
число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;
число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего переменной, вводимой в базис;
число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и ключевой строки.
Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают произведение второго и третьего.
Р0: 150-1∙50=100
240-1∙50=190
Х2: 1-1∙0=1
2-1∙0=2
Х4: 0-1∙0=0
-1-1∙0=-1
Х5: 0-1∙(-1)=1
0-1∙(-1)=1
Опорный план: X=(50;0;100;0;0;190).
Находим оценки:
∆1=0+0+300-300=0
∆2=0-2М+0-200=-200
∆3=0+0+0-0=0
∆4=0+М+0-0=М
∆5=0-М-300-0=-М-300
∆6=0-М+0+М=0
W=0∙50-М∙190+300∙50=-190∙М+15000
Поскольку среди есть отрицательные оценки, то опорный план не является оптимальным