Этап 2 – определяется число нормируемых вкладов при квоте C_p, т.е. число вкладов больше расчетной квоты:

K_норм.=K_общ.-K_{ненорм.,}

где: K_норм. – число нормируемых вкладов (С_j > C_p);

K_{ненорм.} – число ненормируемых вкладов (С_j < C_p);

C_j – вклад j–го источника в суммарную концентрацию.

Этап 3 – определяется новое значение расчетной квоты (C’_p):

C’_p=(N-C_{ненорм.})/K_норм.

Где C_ненорм – сумма вкладов в долях ПДК, не превышающих текущего значения C_p.

Если число нормируемых источников K’_норм. по квоте C’_p меньше числа нормируемых вкладов K’_норм. по квоте C_p, то повторяем этапы 2 и 3, приняв C’_p=C_p.

В противном случае принимаем нормативную квоту C_н= C’_p.

Нормативное значение вклада ИЗА С_{i норм} в долях ПДК принимается равным нормативной квоте C_н:

C_нормj.=C_н

Мощность выброса ЗВ каждого существенного источника снижается пропорционально требуемому снижению вклада в точке:

Q_нормj =Q_j*(С_нормj|/С_j)

В качестве норматива мощности выброса X_j принимается наименьшее значение Q_нормj из рассчитанных во всех точках, где данный источник дает вклад в общую концентрацию.

Другой встречающийся в методической литературе метод расчетного определения ПДВ для группы источников носит название МРН-87 [42]. Суть его заключается в том, что все контрольные точки (где С>N) ранжируются в порядке убывания, после чего расчет начинается с точки 1. Всем источникам, определяющим заданный процент (95%-100%) загрязнения в этой точке устанавливается кратность снижения, равная С/N. На основе свойства линейности загрязнение в остальных точках пересчитывается. Если существуют точки, где превышение С>N сохранятся (там подключаются другие источники), то процедура повторяется. И так до тех пор, пока во всех точках не будет обеспечено соблюдение норматива N (ПДК).

Оба рассмотренных метода дают частное решение ранее рассмотренной системы линейных неравенств (С- существующая концентрация, N- ее нормативное значение, Х - ПДВ) для I контрольных точек (i=1,..,I). Отсутствие целевой функции не позволяет интерпретировать смысл рассчитанных таким образом ПДВ. Опыт работы с этими методами, реализованными в составе ПК ЭРА-ВОЗДУХ, показывает, что в различных случаях то один, то другой дает более выгодные для предприятия результаты в смысле максимального оставшегося после снижения суммарного выброса.

2. Симплекс-метод

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

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

2.1 Общая характеристика симплекс метода

Симплекс метод - это универсальный метод для решения линейных систем уравнений или неравенств и линейного функционала [25].

Общая идея симплекс метода для решения ЗЛП (задачи линейного программирования) состоит в:

• умении находить начальный опорный план;

• наличии признака оптимальности опорного плана;

• умении переходить к нехудшему опорному плану.

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

.

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

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

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

,

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

.

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

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

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

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

входят в левую часть (при ) с коэффициентами, равными –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.

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

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

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