Разработка программного модуля для нахождения оптимальных предельно-допустимых выбросов в атмосферу от группы источников

Пусть ЗЛП представлена системой ограничений в каноническом виде:

 

.

 

Говорят, что ограничение  ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Пусть система ограничений  имеет вид

 

Сведем задачу к каноническому  виду. Для этого прибавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной:

 

,

 

которая имеет предпочтительный вид 

 

.

 

В целевую функцию  дополнительные переменные вводятся с  коэффициентами, равными нулю .

Пусть далее система ограничений имеет вид

 

 

Сведём её к эквивалентной  вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

 

 

Однако теперь система  ограничений не имеет предпочтительного  вида, так как дополнительные переменные

 входят в левую часть (при  ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план

 

 

 

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

Пусть исходная ЗЛП имеет  вид

 

    (2.1)

   (2.2)

      (2.3)

 

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

 

   (2.4)

   (2.5)

  , ,  (2.6)

Задача (2.4)-(2.6) имеет предпочтительный план. Её начальный опорный план имеет вид

 

 

Если некоторые из уравнений (2.2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

 

   (2.7)

 

М-задачи (2.4)-(2.6) все искусственные переменные , то план является оптимальным планом исходной задачи (2.1)-(2.3).

Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный  базис и решают расширенную М-задачу, которая имеет начальный опорный план

Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.

Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые n компоненты дают оптимальный план исходной задачи.

 

Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Признаки оптимальности.

 

Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален.

Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки являются неположительными, то такой план оптимален.

Для привидения системы  ограничений неравенств к каноническому  виду, необходимо в системе ограничений  выделить единичный базис.

1. Ограничения вида «0»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
2. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1». а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
3. Ограничения вида «0» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

 

2.2 Алгоритм симплекс метода (первая симплекс таблица)

 

Пусть система приведена к каноническому  виду.

 

X1+     q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X2+   q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X3+  q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

……………………………………………………………….

Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm

 

В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.

 

Fmin= C1X1+ C2X2+ C3X3+....+ CnXn

 

Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.

Для дальнейших рассуждений  вычислений будем пользоваться первой симплекс таблицей (таблица1).

 

Таблица 1.

C	Б	H	C1	C2	…	Cm	Cm+1	…	Cm+k
			X1	X2	…	Xm	Xm+1	…	Xm+k
C1 C2 C3 : : Cm	X1 X2 X3 : : Xm	h1 h2 h3 : : hm	1 0 0 : : 0	0 1 0 : : 0	: : : : : :	0 0 0 : : 0	q1,m+1 q2,m+1 q3,m+1 : : qm,m+1	: : : : : :	q1,m+k q2,m+k q3,m+k : : qm,m+k
	F=	F0	1		…	m	m+1	…	m+k

 

Первый столбец- коэффициенты в  целевой функции при базисных переменных.

Второй столбец - базисные переменные.

Третий столбец - свободные  члены (hi00).

Самая верхняя строка - коэффициенты при целевой функции.

Вторая верхняя строка - сами переменные, входящие в целевую  функцию и в систему ограничений.

Основное поле симплекс метода - система коэффициентов из уравнения.

Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».

Индексная строка позволяет  нам судить об оптимальности плана:

1. При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
2. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

Переход ко второй итерации:

Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления  элементов столбца H на соответствующие элементы ключевого столбца.

На пересечении строки и столбца находится разрешающий  элемент.

На этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

1. Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
2. Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
3. Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
4. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
5. Остальные элементы переносятся по формуле:

 

 

3. Формализация поставленной задачи

 

Прежде всего, покажем, что характерные свойства МАД  и известные сведения из теории линейных операторов позволяют экспертизу АОМ  и установление ПДВ формализовать  в виде двух зависимых математических задач.

Пусть суммарное загрязнение  ВБ города отдельной примесью характеризуется функцией C(X,t) пространственных координат и времени. Загрязнение считается допустимым при C(X,t) < N(X) _, где N – норматив. Если C(X,t) > N(X), то необходимы АО мероприятия по достижению норматива. При их планировании из суммарного загрязнения атмосферы требуется выделить вклады Cj(X,t), j=1,…,J от J заданных источников, под которыми могут подразумеваться как отдельные трубы, аэрационные фонари и т.д., так и их совокупности, объединенные по различным признакам (по принадлежности к одному цеху, предприятию, ведомству по высоте выброса и т.д.). Пусть выбросы источников есть Q = (Q ₁,Q ₂,…,Q_J). Предположим, что остальные параметры (высота, координаты и т.д.) в результате АОМ не изменяются. Тогда возникающую при экспертизе планов АОМ города задачу - определить изменение dC характеристик загрязнения ВБ по сравнению с базовым (предплановым) периодом – можно записать в виде:

 

dC = C₀ – C_P = A(Q) – A(X) (3.21)

 

где А- оператор модельной  зависимости C от Q; величины C с индексом '₀' относятся к базовому периоду, а с индексом '_P' - к ожидаемому после реализации запланированных АОМ. Заметим, что не только ожидаемый C_P, но и существующий уровень загрязнения C₀, суммарное значение которого в некоторых точках промышленного города регулярно измеряется [78], требует в (1.21) модельного представления C₀ = A(Q₀), поскольку в общем случае методы контроля загрязнения не могут указать вклад конкретного источника в измеряемую величину. Соотношение (3.21) показывает, что формализация выделенной задачи сводится к построению и надлежащему применению оператора А, позволяющего переходить от выбросов к характеристикам загрязнения ВБ и различать заданный источник на фоне всех остальных.

Пользуясь линейностью  модели ОНД-86 по выбросам источников можно  представить загрязнение атмосферы в контрольных точках жилой зоны в виде линейной формы:

 

,

 

где - концентрация в i-ой точке, - выброс j-го источника, - вклад j-го источника в i-й точке, который в дальнейшем будем называть коэффициентом влияния. Отметим, что на практике (поскольку число источников и контрольных точек конечно) оператор А представляет собой матрицу, состоящую из коэффициентов влияния a_ij.

Санитарные требования приводят к системе линейных неравенств:

 

,

 

решение которой ищется на интервале

 

,

 

где - технологически обоснованный минимум выброса j-го источника.

 

На сегодняшний день в методической литературе описаны  два метода нахождения решения поставленной задачи: МРН-87 [24] и метод равного  квотирования [26]. Оба метода кратко рассмотрены в параграфе . Они дают частное решение поставленной системы неравенств из соображений удобства нахождения единственного решения. Однако любое предприятие заинтересовано в минимальных затратах, необходимых для установления нормативных выбросов . Для этой цели, к поставленной системе неравенств добавляем целевую функцию: