Построение оптимального производственного плана химической компании
Содержание
Экономическая постановка задачи........................................................3
Математическая постановка задачи......................................................4
Описание и теоретическое обоснование алгоритма решения.............5
Решение задачи. Стохастическое программировани11
Метод линейных комбинаций...15
Выводы.19
Список использованной литературы.20
Экономическая постановка задачи
Предприятие химической промышленности ЗАО Химсервис планирует выпустить 2 новых вида кислот. С этой целью был проведён ряд исследований, в результате которых стало очевидно, что вред окружающей среде от искомого производства составит соответственно 10 и 20% от всей продукции в стоимостном выражении.
Государство вводит экологические санкции за превышение лимита допустимой концентрации казанных отходов в реке (он составляет 100 литров в квартал).
Себестоимость продукции предприятия прогнозируется независимо по каждому виду товара на основании практических данных по сходным по технологии производства видам, причём достоверность прогноза не менее 0,9 и 0,8 по каждому виду продукции соответственно.
Необходимо произвести оценку себестоимости продукции и составить оптимальный производственный план за квартал, учитывающий данную оценку, если известно, что Химсервис заключил договор поставки с парфюмерной компанией Парфюм, который предусматривает реализацию кислотной продукции по ценам 15 и 20 тысяч рублей за литр соответственно.
Математическая постановка задачи
Исходная задача эквивалентна следующей:
z = (15 - m) * x1 + (20 - n) * x2 Ц > max
x1 + 2 * x2 ≤ 1
P {m ≥ M} ≥ 0.9
P {n ≥ N} ≥ 0.8
В данной символической записи Таблица 1 Оценка себестоимости продукции Описание и теоретическое обоснование алгоритма решения Прежде всего необходимо свести задачу к детерминированному виду. Для этого достаточно знать на заранее известном ровне значимости α законы распределения случайных величин. Определить его можно путём анализа статистических данных, приведённых в таблице 1. При проверке выборок на принадлежность их к закону распределения,
тип которого можно оценить с помощью гистограммы и эмпирической функции распределения,
используется критерий согласия Колмогорова-Смирнова. Определим расстояние Колмогорова между эмпирической и теоретической функциями распределения: Соответствующее решающее правило критерия: H0 верна, если Для того чтобы пользоваться казанным критерием необходимо провести группировку исходной выборки по интервалам, построить соответствующие гистограмму и эмпирическую функции распределения. Наконец, для оценки значений теоретической функции распределения необходимо оценить параметры подбираемого распределения. После становления на ровне значимости α справедливости гипотезы H0 можно преобразовать казанные вероятностные ограничения к эквивалентным детерминированным. Это можно сделать следующим образом: Очевидно, что целевая функция - это функция четырёх переменных, все ограничения модели линейны,
так как преобразованные вероятностные ограничения представляют собой функции распределения с аргументом Теперь можно с полным правом использовать метод линейных комбинаций. Его общая постановка выглядит следующим образом: Здесь X, Ai, Bj - векторы переменных,
соответствующих им коэффициентов и правых частей ограничений соответственно.
Также выполнены словия Суть метода линейных комбинаций заключается в итерационном использовании понятия градиента функции (обозначается Пусть Xk - допустимая точка, полученная на Так как целевая функция Отсюда следует, что точка Xk+1 является линейной комбинацией точек Xk и X*, значит это точки выпуклой области допустимых решений, поэтому точка Xk+1 также является допустимой. Так как Xk+1 зависит лишь от r, то Xk+1 определяется путём максимизации функции Теперь вкратце необходимо описать применение обобщённого симплекс-метода (сочетает в себе прямой и двойственный симплекс методы) для решения задачи линейного программирования. Рассмотрим для начала симплекс-таблицу и правила её
построения. Таблица 2 Пример симплекс-таблицы Базис X1 X2 X3 X4 Решение Z -1 -2 0 0 0 X3 2 1 1 0 3 X4 3 4 0 1 2 Эта таблица представляет собой начальную симплекс-таблицу и эквивалентна следующей задаче линейного программирования: Здесь переменные X3, X4 являются вспомогательными для получения начального базисного решения. Если бы неравенства имели знак ≥, то они вычитались бы из их левых частей. После того как сформировано начальное базисное решение, проводятся операции по его лучшению,
сохраняя при этом допустимость решения. В задаче максимизации целевой функции оптимум достигается тогда и только тогда, когда коэффициенты при небазисных переменных становятся положительными. Итерации симплекс-метода подвергаются условиям оптимальности и допустимости. Условие допустимости: в качестве исключаемой переменной из базиса выбирается такая, для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если переменных с таким свойством несколько, то выбирается любая из них. Условие оптимальности: в качестве вводимой переменной в задаче максимизации является небазисная переменная, имеющая наибольший отрицательный коэффициент в Теперь можно привести последовательность действий прямого симплекс-метода: находится начальное допустимое базисное решение; на основе словия оптимальности определяется вводимая переменная. Если вводимых переменных нет,
вычисления заканчиваются; на основе словия допустимости выбирается исключаемая переменная; методом Гаусса вычисляется новое базисное решение. Переход к шагу 2. К сожалению,
нахождение начального базисного решения можно обеспечить только лишь в случае,
когда все ограничения задачи линейного программирования имеют знак ≤. В противном случае либо используют искусственные переменные, либо используют двойственный симплекс-метод в комбинации с прямым симплекс-методом (обобщённый симплекс-метод). Идея двойственного симплекс-метода состоит в рассмотрении в качестве начального базиса оптимальное, но недопустимое решение (супероптимальное решение). То есть умножают неравенства со знаком ≥ на (-1). Таким образом, если в Условие допустимости: в качестве исключаемой переменной выбирается такая, которая имеет наибольшее по абсолютной величине отрицательное значение. Если все базисные переменные неотрицательны, процесс вычислений заканчивается. Условие оптимальности: вводимая переменная определяется, соответствующая словию Однако, при умножении неравенств со знаком ≥ на (-1) начальное базисное решение может оказаться неоптимальным и недопустимым. В таких случаях применяется обобщённый симплекс-метод: сначала применяем двойственное словие допустимости. Выбор вводимой переменной осуществляется с применением двойственного словия оптимальности. Описанная процедура повторяется до тех пор, пока не будет получено допустимое решение.
Далее применяется прямой симплекс-метод, где начальное базисное решение же соответствует словию допустимости, но не является оптимальным. В завершении обзора алгоритма решения искомой задачи опишем метод анализа чувствительности оптимального решения задачи линейного программирования к изменению коэффициентов целевой функции. Для этого рассмотрим фрагмент симплекс-таблицы и некую задачу линейного программирования в матричном виде: Таблица 3 Фрагмент матричной симплекс-таблицы Базис ЕxjЕ Xб Решение z zj-cj Xб B-1Pj B-1 B-1b Введём теперь понятие двойственной задачи: Обозначим через Y для любой симплекс-таблицы прямой или двойственной задачи справедливо: коэффициент при для любой пары допустимых решений прямой и двойственной задач выполняется: значение целевой функции в задаче максимизации ≤ значения целевой функции в задаче минимизации. В точке оптимума наблюдается строгое равенство. Таблица 4 Соотношение прямой и двойственной задачи Прямая задача Двойственная задача Тем самым можно вычислить новые значения коэффициентов Решение задачи Стохастическое программирование Проведём анализ выборок из генеральных совокупностей M и N на основании данных, приведённых в таблице 1. Для построения таких таблиц необходимо построить точечные оценки параметров распределения генеральных совокупностей. Наилучшими такими оценками для математического ожидания и дисперсии являются выборочное среднее и выборочная дисперсия при неизвестном математическом ожидании соответственно.
Они рассчитываются как Таблица 5 анализ выборки из M Таблица 6 анализ выборки из N Здесь Fт представляет собой расчёт теоретической функции распределения, получаемый при оценивании параметров распределения наилучшими точечными оценками. Закон распределения предполагается нормальным в обоих случаях, так как вид гистограммы, построенной по исходным данным, является схожим графику плотности нормального распределения с параметрами, равными точечным оценкам. рис. 1 Гистограмма M рис. 2 Гистограмма N Так как на основании гистограмм выдвинуто предположение о нормальности законов распределения M и N, то можно окончательно формировать таблицы 5 и 6, где рис 3. Функции распределения M рис 4. Функции распределения N Из рисунков видно,
что данные выборок неплохо согласуются с теоретическими значениями,
следовательно, имеет смысл применить критерий согласия Колмогорова-Смирнова для подтверждения на ровне значимости α = 0,01 гипотезы соответствия эмпирических данных теоретическому распределению. По таблицам 5 и 6
вычисляем значения критериальной статистики при Теперь можно преобразовать стохастические ограничения задачи в эквивалентные им линейные. Заметим, что все преобразования законны, так как M - случайная величина, имеющая на ровне значимости α =
0,01 нормальное распределение с параметрами налогично для случайной величины N: Таким образом,
можно сформулировать задачу нелинейного программирования с линейными ограничениями: Метод линейных комбинаций Выберем произвольную начальную точку, довлетворяющую всем ограничениям задачи: X1 = (1; 1; 12; 4). Теперь можно вычислить градиент исходной целевой функции в точке X1: Поскольку последняя эквивалентность определяет стандартный вид задачи линейного программирования,
можно построить начальную симплекс-таблицу, содержащую неоптимальное и недопустимое решение. Таблица 7 Первая итерация Базис x1 x2 m n S1 S2 S3 Решение w1 -3 -16 1 1 0 0 0 0 S1 1 2 0 0 1 0 0 1 S2 0 0 -25 0 0 1 0 -268 S3 0 0 0 -10 0 0 1 -33 Согласно обобщённому симплекс-методу для поиска исключаемой переменной из базиса пользуемся двойственным словием оптимальности - в данном случае исключаемой будет переменная S2.
В качестве вводимой переменной по двойственному словий оптимальности выберем переменную новая ведущая строка равна текущей строке, делённой на ведущий элемент; новая строка равна разности текущей строки и новой ведущей строки, множенной на её коэффициент в ведущем столбце. Таблица 8 Вторая итерация Базис x1 x2 m n S1 S2 S3 Решение w1 -3 -16 0 1 0 0 S1 1 2 0 0 1 0 0 1 m 0 0 1 0 0 0 S3 0 0 0 -10 0 0 1 -33 Теперь в качестве исключаемой переменной выберем S3, в качестве вводимой - Таблица 9 Третья итерация Базис x1 x2 m n S1 S2 S3 Решение w1 -3 -16 0 0 0 S1 1 2 0 0 1 0 0 1 m 0 0 1 0 0 0 n 0 0 0 1 0 0 Недопустимость решения странена, значит, можно пользоваться прямым симплекс-методом. В качестве вводимой переменной берём Таблица 10 Четвёртая итерация Базис x1 x2 m n S1 S2 S3 Решение w1 5 0 0 0 8 x2 1 0 0 0 0 500 m 0 0 1 0 0 0 n 0 0 0 1 0 0 Текущее решение удовлетворяет словиям оптимальности и допустимости прямого симплекс-метода,
следовательно, в таблице 10 содержится оптимальное решение задачи линейного программирования w1. Запишем вектор, соответствующий данному решению: Для завершения решения задачи линейного программирования Пусть коэффициенты целевой функции Теперь можно вычислить коэффициенты В итоге словие (1)
является необходимым и достаточным для того, чтобы тверждать состоятельность текущего базисного решения при изменении коэффициентов целевой функции. Так как Подставляя в формулу (2) вычисленный ранее вектор X*, получим: X2 = ( 1; 1; 12; 4 ) + r ( -1; 499; Согласно методу линейных комбинаций вычислим максимум целевой функции В итоге данная функция относительно r является квадратичной с положительным старшим коэффициентом - значит, своего минимума она достигнет при отрицательном r. Очевидно, при всех допустимых r функция монотонно возрастает - её
максимум совпадает с максимальных допустимым r. То есть Вычислим градиент искомой целевой функции в точке X2 и составим соответствующую задачу линейного программирования: Проверим коэффициенты текущей задачи линейного программирования на чувствительность,
используя формулу (1): Выводы Использованные в задаче методы позволяют разрешить довольно широкий класс задач нелинейного программирования. Однако, они не являются ниверсальными, в частности, метод линейных комбинаций рассматривает лишь линейные ограничения. В реальной действительности всё далеко не так просто: любая фирма функционирует в конкурентной рыночной среде - задача максимизации прибыли должна учитывать принятие правленческих решений (стратегий), позволяющих предугадать поведение конкурентов. К тому же, каким бы хорошим не было решение задачи, всегда в реальной жизни необходимо руководствоваться здравым смыслом и трактовать полученные результаты применительно к конкретной ситуации, которая, как известно, всегда несколько отличается от теоретических положений. Для соответствия полученныха теоретических данных экспериментальным возможно понадобится более сложная структура методов. Список использованной литературы 1. Таха Х. А. Введение в исследование операций // М.: Вильямс, 2001. 2. Смородинский С. С., Батин Н. В.
Оптимизация решений на основе методов и моделей математического программирования // Минск: БГУИР, 2003 3. Степанова М. Д. Проверка статистических гипотез // Минск: БГУИР, 2 4. Волковец А. И., Гуринович А. Б. Теория вероятностей и математическая статистика // Минск: БГУИР, 2003 5. Лутманов С. В. Линейные задачи оптимизации // Пермь: Пермский н-т, 2004
H1. Здесь статистика 
апри достаточно большом
X же здесь представлен в виде: 
ана отрезке [Xk,X*] должна существовать точка Xk+1, такая, что 
ó 
аи 
M и N:
а<- значит гипотеза верна.
а<- гипотеза также верна.
аимеет нормированное нормальное распределение с математическим ожиданием, равным нулю, и единичной дисперсией. Значит, функция распределения такой случайной величины будет эквивалентна табулируемой функции Лапласа, что позволяет в силу монотонности последней преобразовать эквивалентным образом стохастическое ограничение в линейное.
ó 
ó
.
ó 
(1)
X2:
(2)
; 
1- r; 1+
499r; 12 ; 4 ).
X2 = ( 0; 500; 
.
. Ввиду равенства X* = X2, имеем:
X2 является искомым оптимальным вектором, а максимальное значение целевой функции z составляет zmax = 8350.