Построить математическую модель задачи оптимизации производства

Если бы фирма выпускала только шляпы фасона 2, суточный объем производства мог бы составить 60*2 = 120 шляп. Пусть фирма выпускает в сутки x1 шляп фасона 1 и x2 шляп фасона 2.
Создадим математическую модель задачи сформулировав целевую функцию и ограничения.
-1276352825758x1+5x2 → max
x1 ≤ 60
x2 ≤ 120
 x1 + x2 ≥ 50
 x1 + x2 ≤ 100
 x ≥ 0 , y ≥ 0 .
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 4-м неравенстве смысла (≤) вводим базисную переменную x6.
x1+x3 = 60
x2+x4 = 120
x1+x2-x5 = 50
x1+x2+x6 = 100
Расширенная матрица системы ограничений-равенств данной задачи:
EQ \b\bc\| (\a \al \co7 \hs4 (1;0;1;0;0;0;60;0;1;0;1;0;0;120;1;1;0;0;-1;0;50;1;1;0;0;0;1;100))
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
Получаем новую матрицу:
1 0 1 0 0 0 60
0 1 0 1 0 0 120
-1 -1 0 0 1 0 -50
1 1 0 0 0 1 100
4. В качестве базовой переменной можно выбрать x6.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5,6).
Выразим базисные переменные через остальные:
x3 = -x1+60
x4 = -x2+120
x5 = x1+x2-50
x6 = -x1-x2+100
Подставим их в целевую функцию:
F(X) = 8x1+5x2
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x5 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6
x3 60 1 0 1 0 0 0
x4 70 -1 0 0 1 1 0
x2 50 1 1 0 0 -1 0
x6 50 0 0 0 0 1 1
F(X0) -250 3 0 0 0 5 0
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
60-(-50*0):-1 1-(-1*0):-1 0-(-1*0):-1 1-(0*0):-1 0-(0*0):-1 0-(1*0):-1 0-(0*0):-1
120-(-50*1):-1 0-(-1*1):-1 1-(-1*1):-1 0-(0*1):-1 1-(0*1):-1 0-(1*1):-1 0-(0*1):-1
-50 : -1 -1 : -1 -1 : -1 0 : -1 0 : -1 1 : -1 0 : -1
100-(-50*1):-1 1-(-1*1):-1 1-(-1*1):-1 0-(0*1):-1 0-(0*1):-1 0-(1*1):-1 1-(0*1):-1
Выразим базисные переменные через остальные:
x3 = -x1+60
x4 = x1-x5+70
x2 = -x1+x5+50
x6 = -x5+50
Подставим их в целевую функцию:
F(X) = 8x1+5(-x1+x5+50)
или
F(X) = 3x1+5x5+250
x1+x3=60
-x1+x4+x5=70
x1+x2-x5=50
x5+x6=50
При вычислениях значение Fc = 250 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
EQ A = \b(\a \al \co6 \hs4 (1;0;1;0;0;0;-1;0;0;1;1;0;1;1;0;0;-1;0;0;0;0;0;1;1))
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом .
Решим систему уравнений относительно базисных переменных: x3, x4, x2, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,50,60,70,0,50)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6
x3 60 1 0 1 0 0 0
x4 70 -1 0 0 1 1 0
x2 50 1 1 0 0 -1 0
x6 50 0 0 0 0 1 1
F(X0) 0 -3 0 0 0 -5 0
Переходим к основному алгоритму симплекс-метода.
Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю.
Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai5
и из них выберем наименьшее:
min (- , 70 : 1 , - , 50 : 1 ) = 50
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x3 60 1 0 1 0 0 0 -
x4 70 -1 0 0 1 1 0 70
x2 50 1 1 0 0 -1 0 -
x6 50 0 0 0 0 1 1 50
F(X1) 0 -3 0 0 0 -5 0 0
Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x5.
Строка, соответствующая переменной x5 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x5 записываем нули.
Таким образом, в новом плане 1 заполнены строка x5 и столбец x5. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
60-(50*0):1 1-(0*0):1 0-(0*0):1 1-(0*0):1 0-(0*0):1 0-(1*0):1 0-(1*0):1
70-(50*1):1 -1-(0*1):1 0-(0*1):1 0-(0*1):1 1-(0*1):1 1-(1*1):1 0-(1*1):1
50-(50*-1):1 1-(0*-1):1 1-(0*-1):1 0-(0*-1):1 0-(0*-1):1 -1-(1*-1):1 0-(1*-1):1
50 : 1 0 : 1 0 : 1 0 : 1 0 : 1 1 : 1 1 : 1
0-(50*-5):1 -3-(0*-5):1 0-(0*-5):1 0-(0*-5):1 0-(0*-5):1 -5-(1*-5):1 0-(1*-5):1
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x3 60 1 0 1 0 0 0
x4 20 -1 0 0 1 0 -1
x2 100 1 1 0 0 0 1
x5 50 0 0 0 0 1 1
F(X1) 250 -3 0 0 0 0 5
Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (60 : 1 , - , 100 : 1 , - ) = 60
Следовательно, 1-ая строка является ведущей