Линейное программирование. Разработка оптимального плана производства

1. Линейное программирование 1.1. Разработка оптимального плана производства Использование модели линейного программирования для определения плана производства. Общая постановка задачи планирования производства: определить план производства одного или нескольких видов продукции, обеспечивающий наиболее рациональное использование имеющихся материальных, финансовых и других видов ресурсов. План должен быть оптимальным с точки зрения выбранного критерия – максимум прибыли, минимум затрат на производство и т.д. Формально задача оптимизации производственной программы может быть описана с помощью следующей модели линейного программирования: n  f ( x )  f ( x , x ,..., x )  c j * x j  max  1 2 n  j 1   n  aij * x j  bi , i  1,..., m  j 1  x j  0, j  1,..., n   где n – число выпускаемых видов продукции, m – количество используемых производственных ресурсов, aij - объем затрат ресурса i на единицу выпуска продукта j c j - прибыль от выпуска и реализации единицы продукта j bi - количество имеющегося ресурса i x j - переменная, представляющая объем выпуска продукта j f ( x)  f ( x1, x2 ,..., xn ) - целевая функция, в данном случае прибыль от реализации всей выпущенной продукции. В модели использована система ограничений на объем фактически имеющихся ресурсов и система общих ограничений в виде неотрицательности переменных. Задача в такой постановке называется задачей линейного программирования в стандартной форме на максимум. Вектор x  ( x1, x2 ,..., xn ) , компоненты которого удовлетворяют всем ограничениям называется допустимым решением или допустимым планом задачи линейного программирования. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимый план, на котором целевая функция достигает своего максимального значения называется оптимальным решением или оптимальным планом решения задачи линейного программирования. Если при сохранении всех ограничений необходимо искать не максиn мум, а минимум целевой функции f ( x)  f ( x1, x2 ,..., xn )   c j * x j  min , то j 1 такую задачу легко свести к исходной. Для этого рассмотрим новую целевую функцию n n n j 1 j 1 j 1 g ( x)   f ( x)   f ( x1, x2 ,..., xn )   c j * x j   c j * x j   c j * x j где c j  c j . Для новой целевой функции g ( x) получаем стандартную задачу на максимум: g ( x)  max . С каждой задачей линейного программирования связана стандартным образом другая задача, которая называется двойственной задачей линейного программирования. m  h( y )  h( y1 , y2 ,..., ym )   bi * yi  min i 1  m   aij * yi  c j , j  1,..., n  i 1  yi  0, i  1,..., m   Независимых переменных yi столько, сколько ограничений в исходной задаче. Коэффициенты новой целевой функции равны правым частям исходных ограничений. Матрица коэффициентов ограничений есть транспонированная исходная матрица, а сами ограничения есть коэффициенты исходной целевой функции, при этом знак ограничений меняется на противоположный. Двойственная к исходной задаче есть исходная задача линейного программирования. Если какая-либо из задач имеет решение, то и другая задача также имеет решение, причем оптимальные значения целевых функций совпадают: Max[ f ( x1, x2 ,..., xn )]  Min[h( y1, y2 ,..., ym )] Компоненты yi* оптимального решения двойственной задачи называютn ся двойственной оценкой ограничения a j 1 ij * x j  bi исходной задачи. Введем оптимальное значение целевой функции ( x* )  Max[ f ( x1, x2 ,..., xn )] и рассмотрим ее частную производную по ограничению bi .  Тогда ( x* )  yi* , i  1,..., m , то есть при изменении ограничения bi на bi достаточно малую величину bi , оптимальное значение целевой функции  изменится на ( x* )  ( x* ) * bi  yi* * bi . Например, если bi  1 , то bi ( x* )  yi* (если изменение на 1 можно считать достаточно малым). Если коэффициент целевой функции c j изменится на c j , то оптимальное значение целевой функции ( x* ) изменится на ( x* )  c j * x*j . Стандартный алгоритм решения прямой и двойственной задачи основан на симплекс-методе. Этот метод и его модификации подробно описаны в учебной литературе. Один из вариантов симплекс-метода реализован в Wolfram Mathematica в виде стандартных функций LinearProgramming и DualLinearProgramming. Список обязательных аргументов этих функций: c  {c1, c2 ,..., cn } – вектор коэффициентов исходной целевой функции,  a1,1 , a1,2 ,..., a1,n    a , a ,..., a 2,1 2,2 2, n  – матрица коэффициентов ограничений, a  ...     a , a ,..., a  m ,1 m ,2 m , n    b1 , s1    b2 , s2   - матрица коэффициентов ограничений и признаков типа огb  ...     bm , sm  si  1, если ограничение меньше или равно раничения, причем si  1, если ограничение больше или равно si  0, если ограничение типа равенства 1.2. Пример решения задачи. Кооператив по производству строительных материалов выпускает два вида стройматериалов: жидкое стекло и пенопласт. Трудозатраты на производство 1 т стекла – 20 ч, пенопласта – 10 ч. В кооперативе работают 10 рабочих по 40 ч в неделю. Оборудование позволяет производить не более 15 т стекла и 30 т пенопласта в неделю. Прибыль от реализации 1 т жидкого стекла – 50 руб, 1 т пенопласта – 40 руб. Сколько стройматериалов каждого вида следует выпускать кооперативу для получения максимальной прибыли? Обозначения: x1 - объем производства жидкого стекла в неделю в тоннах, x2 - объем производства пенопласта в неделю в тоннах. Модель для задачи представляет собой задачу линейного программирования:  f ( x)  50 x1  40 x2  max  20 x1  10 x2  400   x1  15  x  30  2  x1  0, x2  0 Первое ограничение – ограничение на фонд рабочего времени, второе и третье – ограничение на выпуск продукции и естественные ограничения типа неотрицательности независимых переменных. Исходные данные для стандартной функции Wolfram Mathematica: c  {50.0,40.0}  20 10  a   1 0  0 1    400 1 b   15 1  30 1   Вызов функции result  LinearProgramming[c, a, b] . Обратить внимание на знак перед вектором c , знак минус означает, что мы решаем задачу максимизации. Стандартная функция LinearProgramming решает, по умолчанию задачу минимизации. Результат {5.0, 30.0}, то есть оптимальное решение x1*  5.0, x2*  30.0 . Полный код на WL  20 10   400 1   c  {50.0,40.0}; a   1 0  ; b   15 1 ; 0 1  30 1     result  LinearProgramming[c, a, b] c.result Исследование решения. Вычислим значение целевой функции c.result , результат 1450.0, операция Dot, задаваемая в виде точки (.), то есть ответ f ( x1* , x2* )  1450.0 . Пусть теперь прибыль от реализации 1 т жидкого стекла увеличится на 1 руб., то есть будет c1  1, c1  51.0 , тогда прибыль увеличится на f  c1 * x1*  1*5.0  5.0 , то есть прибыль возрастет на 5 руб. Проверка активности ограничений, для этого вычислим a.result . Получим {400.0, 5.0, 30.0} или, сравнивая с первой колонкой матрицы b, получим, что активными являются первое и третье ограничения и пассивными только второе. Что произойдет, если общий фонд рабочего времени возрастет на 10 ч? Для это необходимо решить двойственную задачу линейного программирования  20 10   400 1   c  {50.0,40.0}; a   1 0  ; b   15 1 ; 0 1  30 1     resultdual  DualLinearProgramming[c, a, b] Переменная resultdual  {{5.0,30.0},{2.5,0.0, 15.0},{0,0},{0,0}} . Первый ее элемент – это решение исходной задачи, а второй элемент resultdual[[2]] дает двойственные оценки: {2.5,0, 15.0} . Но это оценки для решения задачи минимизации, а у нас решается задача максимизации, поэтому двойственные оценки необходимо брать с противоположным знаком. b  1, то ( x* )   y* * b  2.5 1 1  1  Следовательно, если b2  1, то ( x* )   y2* * b2  0.0  b3  1, то ( x* )   y3* * b3  15.0   Видно, что на ответ влияют только активные ограничения, второе ограничение пассивно, поэтому приращение равно нулю.