Содержание
Экономическая постановказадачи........................................................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 ≤ 1000
P {m ≥ M} ≥ 0.9
P {n ≥ N} ≥ 0.8
В даннойсимволической записи x1, x2,m, n, M, Nпредставляют собой, соответственно,количество планируемой к производству кислоты по видам, себестоимость продукциипо видам и их минимально возможные показатели, представленные случайнымивеличинами. Известна также информация оценки себестоимости продукции потехнологически сходным видам.
Таблица 1
Оценка себестоимости продукции
Описание и теоретическое обоснование алгоритма решения
Прежде всегонеобходимо свести задачу к детерминированному виду. Для этого достаточно знатьна заранее известном уровне значимости α законы распределения случайныхвеличин. Определить его можно путём анализа статистических данных, приведённыхв таблице 1. При проверке выборок на принадлежность их к закону распределения,тип которого можно оценить с помощью гистограммы и эмпирической функции распределения,используется критерий согласия Колмогорова-Смирнова.
Определимрасстояние Колмогорова между эмпирической и теоретической функциямираспределения:
Соответствующеерешающее правило критерия: H0верна, если H1. Здесь статистика при достаточно большомnасимптотически стремится краспределению Колмогорова, которое не зависит от F(x).
Для того чтобыпользоваться указанным критерием необходимо провести группировку исходнойвыборки по интервалам, построить соответствующие гистограмму и эмпирическуюфункции распределения. Наконец, для оценки значений теоретической функциираспределения необходимо оценить параметры подбираемого распределения.
После установленияна уровне значимости α справедливости гипотезы H0можно преобразовать указанные вероятностныеограничения к эквивалентным детерминированным. Это можно сделать следующимобразом:
Xже здесь представлен в виде:
Очевидно, чтоцелевая функция – это функция четырёх переменных, все ограничения модели линейны,так как преобразованные вероятностные ограничения представляют собой функциираспределения с аргументом
Теперь можно сполным правом использовать метод линейных комбинаций. Его общая постановкавыглядит следующим образом:
Здесь X, Ai, Bj– векторы переменных,соответствующих им коэффициентов и правых частей ограничений соответственно.Также выполнены условия k
Суть методалинейных комбинаций заключается в итерационном использовании понятия градиентафункции (обозначается gradz). По определений градиент функциизаписывается математически как
n-мерный вектор, координаты которогопредставлены частными производными соответствующей функции (важно заметить, чтофункция zдолжнаиметь конечные частные производные). Градиент покатывает направление, придвижении по которому можно достичь максимума функции на минимальное числоитераций, позволяющих на основании исходных координат вектора переменныхсформировать новый вектор переменных, который будут находиться ближе коптимуму. Очевидно, что данный подход (он основан на равенстве gradz=0, которое в силу определения градиентаэквивалентно необходимому условию существования экстремума у функции z) может вывести за пределы областиограничений задачи. К тому же, в точке условного оптимума градиент функции zне обязательно равен нулю. Поэтомуприменяется следующий алгоритм решения задачи.
Пусть Xk– допустимая точка, полученная на k-ой итерации. Раскладывая исходнуюфункцию в ряд Тейлора, имеем Xи Xk– векторы. Необходимо определитьдопустимую точку X=X*, в которойдостигается максимум функции f(X)привыполнении линейных ограничений задачи. Так как — постоянноеслагаемое, задача определения X*сводится к решению задачи линейного программирования:
Так как целеваяфункция wkопределяется градиентом функции f(X)в точке Xk,улучшение имеющегося решения может быть обеспечено тогда и только тогда, когда f(X*) > f(Xk), так как X*не обязательно находится в малой окрестности точки Xk. Но при выполнении условия на отрезке [Xk,X*] должна существовать точка Xk+1, такая, что f(Xk+1) > f(Xk).Следовательно, задача сводится к нахождению такой точки Xk+1. Определим указанную точку следующимобразом:
Отсюда следует, чтоточка Xk+1 является линейной комбинацией точек Xkи X*, значит это точки выпуклой области допустимыхрешений, поэтому точка Xk+1также является допустимой. Так как Xk+1 зависит лишь от r, то Xk+1определяется путём максимизациифункции k-ой итерации небудет выполнено условие Xkсчитается наилучшим решением.Поскольку задачи линейного программирования, возникающие на каждой итерации,отличаются друг от друга лишь коэффициентами целевой функции, можно применитьанализ чувствительности к соответствующим изменениям.
Теперь вкратценеобходимо описать применение обобщённого симплекс-метода (сочетает в себепрямой и двойственный симплекс методы) для решения задачи линейногопрограммирования. Рассмотрим для начала симплекс-таблицу и правила еёпостроения.
Таблица 2
Пример симплекс-таблицы
Базис
X1
X2
X3
X4
Решение
Z
-1
-2
X3
2
1
1
3
X4
3
4
1
2
Эта таблицапредставляет собой начальную симплекс-таблицу и эквивалентна следующей задачелинейного программирования:
ó
Здесь переменные X3, X4являются вспомогательными для получения начального базисногорешения. Если бы неравенства имели знак ≥, то они вычитались бы из ихлевых частей.
После того каксформировано начальное базисное решение, проводятся операции по его улучшению,сохраняя при этом допустимость решения. В задаче максимизации целевой функцииоптимум достигается тогда и только тогда, когда коэффициенты при небазисныхпеременных становятся положительными. Итерации симплекс-метода подвергаютсяусловиям оптимальности и допустимости.
Условиедопустимости: в качестве исключаемой переменной из базиса выбирается такая, длякоторой отношение значения правой части ограничения к положительномукоэффициенту ведущего столбца минимально. Если переменных с таким свойствомнесколько, то выбирается любая из них.
Условиеоптимальности: в качестве вводимой переменной в задаче максимизации являетсянебазисная переменная, имеющая наибольший отрицательный коэффициент в z-строке. Если переменных с такимсвойством несколько, то выбирается любая из них.
Теперь можнопривести последовательность действий прямого симплекс-метода:
находится начальноедопустимое базисное решение;
на основе условияоптимальности определяется вводимая переменная. Если вводимых переменных нет,вычисления заканчиваются;
на основе условиядопустимости выбирается исключаемая переменная;
методом Гауссавычисляется новое базисное решение. Переход к шагу 2.
К сожалению,нахождение начального базисного решения можно обеспечить только лишь в случае,когда все ограничения задачи линейного программирования имеют знак ≤. Впротивном случае либо используют искусственные переменные, либо используютдвойственный симплекс-метод в комбинации с прямым симплекс-методом (обобщённыйсимплекс-метод).
Идея двойственногосимплекс-метода состоит в рассмотрении в качестве начального базисаоптимальное, но недопустимое решение (супероптимальное решение). То естьумножают неравенства со знаком ≥ на (-1). Таким образом, если в z-строке находится изначальнооптимальное решение, то применим двойственный симплекс-метод.
Условиедопустимости: в качестве исключаемой переменной выбирается такая, которая имеетнаибольшее по абсолютной величине отрицательное значение. Если все базисныепеременные неотрицательны, процесс вычислений заканчивается.
Условиеоптимальности: вводимая переменная определяется, соответствующая условию arj– коэффициент из симплекс-таблицы,расположенный на пересечении ведущей строки (соответствующей исключаемойпеременной xr), соответствующего переменной xj. При наличии альтернативы выборделается произвольно.
Однако, приумножении неравенств со знаком ≥ на (-1) начальное базисное решение может оказаться неоптимальным инедопустимым. В таких случаях применяется обобщённый симплекс-метод: сначалаприменяем двойственное условие допустимости. Выбор вводимой переменнойосуществляется с применением двойственного условия оптимальности. Описаннаяпроцедура повторяется до тех пор, пока не будет получено допустимое решение.Далее применяется прямой симплекс-метод, где начальное базисное решение ужесоответствует условию допустимости, но не является оптимальным.
В завершении обзораалгоритма решения искомой задачи опишем метод анализа чувствительности оптимальногорешения задачи линейного программирования к изменению коэффициентов целевойфункции. Для этого рассмотрим фрагмент симплекс-таблицы и некую задачулинейного программирования в матричном виде:
Таблица 3
Фрагмент матричной симплекс-таблицы
Базис
…xj…
Xб
Решение
z
zj-cj
Xб
B-1Pj
B-1
B-1b
Введём теперьпонятие двойственной задачи:
Обозначим через Ym-мерный вектор переменныхдвойственной задачи. В компактной матричной форме можно записать Y=CбB-1, где Cб– m-мерный вектор, состоящий из коэффициентов cjисходной целевой функции,соответствующих базисному вектору Xб. Таким образом, разности zj-cjможно определить следующим образом:
для любойсимплекс-таблицы прямой или двойственной задачи справедливо: коэффициент при j-ой переменной в z-строке одной задачи равен разностимежду левой и правой частями j-го неравенства другой задачи;
для любой пары допустимыхрешений прямой и двойственной задач выполняется: значение целевой функции взадаче максимизации ≤ значения целевой функции в задаче минимизации. Вточке оптимума наблюдается строгое равенство.
Таблица 4
Соотношение прямой и двойственной задачи
Прямая задача
Двойственная задача
Тем самым можновычислить новые значения коэффициентов z-строки окончательнойсимплекс-таблицы по изменённым исходным данным задачи. В этом и состоит сутьанализа чувствительности к изменению коэффициентов целевой функции. В задачемаксимизации на коэффициенты при небазисных переменных z-строки накладываются ограничениянеотрицательности, что позволяет найти интервалы допустимости для коэффициентовцелевой функции, либо составить систему неравенств, описывающую их.
Решение задачи
Стохастическое программирование
Проведём анализвыборок из генеральных совокупностей Mи Nна основании данных, приведённых втаблице 1. Для построения таких таблиц необходимо построить точечные оценкипараметров распределения генеральных совокупностей. Наилучшими такими оценкамидля математического ожидания и дисперсии являются выборочное среднее ивыборочная дисперсия при неизвестном математическом ожидании соответственно.Они рассчитываются как niи xi– частотаи середина i-го интервала соответственно.Подставляя в формулы данные таблицы 1 и учитывая группировки данных,представленных в таблицах 5 и 6, имеем:
Таблица 5
Анализ выборки из M
Таблица 6
Анализ выборки из N
Здесь Fтпредставляет собой расчёт теоретической функциираспределения, получаемый при оценивании параметров распределения наилучшимиточечными оценками. Закон распределения предполагается нормальным в обоихслучаях, так как вид гистограммы, построенной по исходным данным, являетсясхожим графику плотности нормального распределения с параметрами, равнымиточечным оценкам.
рис. 1 Гистограмма M
рис. 2 Гистограмма N
Так как наосновании гистограмм выдвинуто предположение о нормальности законовраспределения Mи N, то можно окончательно формировать таблицы 5 и 6, где и Mи N:
рис 3. Функциираспределения M
рис 4. Функциираспределения N
Из рисунков видно,что данные выборок неплохо согласуются с теоретическими значениями,следовательно, имеет смысл применить критерий согласия Колмогорова-Смирнова дляподтверждения на уровне значимости α = 0,01 гипотезы соответствияэмпирических данных теоретическому распределению.
По таблицам 5 и 6вычисляем значения критериальной статистики при n= 30.
— значит гипотезаверна.
— гипотеза такжеверна.
Теперь можнопреобразовать стохастические ограничения задачи в эквивалентные им линейные.
Заметим, что всепреобразования законны, так как M– случайная величина, имеющая на уровне значимости α =0,01 нормальное распределение с параметрами имеет нормированноенормальное распределение с математическим ожиданием, равным нулю, и единичнойдисперсией. Значит, функция распределения такой случайной величины будетэквивалентна табулируемой функции Лапласа, что позволяет в силу монотонностипоследней преобразовать эквивалентным образом стохастическое ограничение влинейное.
Аналогично дляслучайной величины N:
Таким образом,можно сформулировать задачу нелинейного программирования с линейнымиограничениями:
ó
Метод линейных комбинаций
Выберемпроизвольную начальную точку, удовлетворяющую всем ограничениям задачи: X1= (1; 1; 12; 4). Теперь можно вычислить градиентисходной целевой функции в точке X1:
ó
Поскольку последняяэквивалентность определяет стандартный вид задачи линейного программирования,можно построить начальную симплекс-таблицу, содержащую неоптимальное инедопустимое решение.
Таблица 7
Первая итерация
Базис
x1
x2
m
n
S1
S2
S3
Решение
w1
-3
-16
1
1
S1
1
2
1
1000
S2
-25
1
-268
S3
-10
1
-33
Согласнообобщённому симплекс-методу для поиска исключаемой переменной из базисапользуемся двойственным условием оптимальности – в данном случае исключаемойбудет переменная S2.В качестве вводимой переменной по двойственному условий оптимальности выберемпеременную m. Тем самым можно формировать следующую симплекс-таблицу. Получить новуюсимплекс-таблицу можно, используя метод Гаусса:
новая ведущаястрока равна текущей строке, делённой на ведущий элемент;
новая строка равнаразности текущей строки и новой ведущей строки, умноженной на её коэффициент введущем столбце.
Таблица 8
Вторая итерация
Базис
x1
x2
m
n
S1
S2
S3
Решение
w1
-3
-16
1
S1
1
2
1
1000
m
1
S3
-10
1
-33
Теперь в качествеисключаемой переменной выберем S3, а в качестве вводимой – n.
Таблица 9
Третья итерация
Базис
x1
x2
m
n
S1
S2
S3
Решение
w1
-3
-16
S1
1
2
1
1000
m
1
n
1
Недопустимостьрешения устранена, значит, можно пользоваться прямым симплекс-методом. Вкачестве вводимой переменной берём x2(имеет наибольший по модулю отрицательныйкоэффициент). Исключаемая из базиса переменная – S1, так как отношение числа в столбце Решение ведущейстроки к ведущему элементу минимально по модулю).
Таблица 10
Четвёртая итерация
Базис
x1
x2
m
n
S1
S2
S3
Решение
w1
5
8
x2
1
500
m
1
n
1
Текущее решениеудовлетворяет условиям оптимальности и допустимости прямого симплекс-метода,следовательно, в таблице 10 содержится оптимальное решение задачи линейногопрограммирования w1. Запишем вектор, соответствующий данному решению: .
Для завершениярешения задачи линейного программирования w1необходимо провести анализ текущего оптимальногорешения на чувствительность. Имея формулировку прямой задачи, можно составитьдвойственную задачу:
ó
Пусть коэффициентыцелевой функции w1изменились, и вектор коэффициентов Cзапишется в виде: C= ( 3 + d1; 16 + d2; -1 + d3; -1 + d4). Так как текущее оптимальное решение представленобазисными переменными x2, m, n, то вектор базисных коэффициентов будет включать именно эти переменные: Cб= ( 16 + d2; -1 + d3; -1 + d4), а обратная матрица B-1– состоять из элементов таблицы 10,соответствующих по своему положению начальному базисному решению. Значит,вектор оптимальных двойственных переменных Yбудет рассчитываться:
Теперь можновычислить коэффициенты z-строки при небазисных переменных, учитывая фундаментальноесоотношение между прямой и двойственной задачами:
(1)
В итоге условие (1)является необходимым и достаточным для того, чтобы утверждать состоятельностьтекущего базисного решения при изменении коэффициентов целевой функции.
Так как X2:
(2)
Подставляя вформулу (2) вычисленный ранее вектор X*, получим:
X2 = ( 1; 1; 12; 4 ) + r ( -1; 499; ; 1- r; 1+499r; 12 ; 4 ).
Согласно методулинейных комбинаций вычислим максимум целевой функции zв точке X2:
В итоге даннаяфункция относительно rявляется квадратичной с положительным старшим коэффициентом– значит, своего минимума она достигнет при отрицательном r. Очевидно, при всех допустимых rфункция монотонно возрастает – еёмаксимум совпадает с максимальных допустимым r. То есть X2= ( 0; 500; .
Вычислим градиентискомой целевой функции в точке X2и составим соответствующую задачу линейного программирования:
Проверимкоэффициенты текущей задачи линейного программирования на чувствительность,используя формулу (1):
. Ввиду равенства X* = X2, имеем:
X2 является искомым оптимальным вектором, амаксимальное значение целевой функции z составляет zmax= 8350.
Выводы
Использованные взадаче мет