Математическое программирование

Задача 1

Кондитерская фабрика для производства двух видов карамели К1 и К2 использует три вида основного сырья: сахар, патоку, фруктовое пюре. Нормы расхода сырья каждого вида на производство 1 т. карамели К1 – 0,5; 0,4; 0,1 соответственно, на производство 1 т. карамели К2 – 0,8; 0,3; 0,1 соответственно. Общий запас сахара – 80 т., патоки – 60 т., фруктового пюре – 12 т. Прибыль от

следующим условиям-ограничениям по затратам cырья:

0,5 x1+0,8 x2 80 ;

0,4 x1+0,3 x2 60 ; 0,1 x1+0,1 x2 12 ; x1 0, x2 0.

вполне подойдет. Строим вектор c(108;112) . Проводим через точку M прямую π , перпендикулярную вектору с . Далее перемещаем эту прямую параллельно самой себе по направлению вектора с , пока она не займет относительно области OABC крайнего верхнего положения. Это произойдет, когда она пройдет через точку B.

Таким образом, оптимальное решение определяется координатами точки B. Так как в точке B пересекаются прямые, отвечающие первому и третьему неравенствам, то ее координаты находим из решения системы уравнений

0,5 x1+0,8 x2=80;

0,1 x1+0,1 x2=12.

x1=1603 ; x2= 2003 .

Следовательно, кондитерская фабрика должна производить 160/3 т. карамели вида К1 и 200/3 т. карамели вида К2, при этом ее доход будет составлять

108 1603 +112 2003 =396803 ≈13226,667 тыс.рублей.

в) Решение задачи симплекс-методом

Прежде всего приведем задачу к каноническому виду, вводя в каждое основное неравенство свою дополнительную переменную yi при ограничениях:

0,5 x1+0,8 x2+ y1=80 ;

0,4 x1+0,3 x2+ y2=60 ; 0,1 x1+0,1 x2+ y3=12 ;

x1 0, x2 0, y1 0, y2 0, y3 0.

Найти max(108 x1+112 x2+0 y1+0 y2+0 y3) .

Отметим, что правые части системы уравнений неотрицательны, система

которые могут считаться базисными переменными начального базисного решения x1=0, x2 =0, y1=80, y2=60, y3=12 . Отметим так же, что функция f не содержит базисных переменных. Значение функции f для начального

случая. Если в симплекс таблице, на каком-то шаге, мы получим строку f , состоящую из неотрицательных элементов – задача решена, мы нашли оптимальное решение. В противном случае – функция не является ограниченной.

Шаг 1

За ведущий выберем столбец 2 , так как -112 – наименьший элемент в f - строке. Элемент f строки, принадлежащий столбцу свободных членов не рассматриваем. За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Отметим, что отношение мы вычисляем только для положительных элементов столбца 2.

От элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на 0,3. От элементов строки 3 отнимаем соответствующие элементы строки 1, умноженные на 0,1. От элементов строки f отнимаем соответствующие элементы строки 1, умноженные на -112.

За ведущий выберем столбец 1 , так как -38 наименьший элемент в f - строке. Элемент f строки, принадлежащий столбцу свободных членов не рассматриваем. За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Отметим, что отношение мы вычисляем только для положительных элементов столбца 1.