Файл: Чесноков, Н. И. Оптимизация решений при разработке урановых месторождений.pdf

(скользящие) переменные и для технологии 1 записы­ ваем следующие условия:

Кроме указанных условий, следует отметить также, что все переменные, входящие в целевую функцию, и ог­ раничения могут принимать только положительные значения. Как видно из целевой функции (3.56) и огра­ ничений (3.57)— (3.66), поставленная задача является типичной задачей линейного программирования. Будем решать ее симплекс-методом, как наиболее широко рас­ пространенным и наиболее простым.

В рассматриваемой задаче 16 неизвестных, однако уравнений всего 10. Таким образом, могут быть выбра­ ны любые 6 неизвестных. Для определения допустимого базисного решения выбранные 6 переменных прини­ маются за нуль. Пусть этими 6 неизвестными являются х'п = Xi2 = X33=X41= Х42 = г'з=0. Тогда решение системы 10

уравнений с 10 неизвестными дает следующие значения:

Этим решением заканчивается подготовка необходимых данных для определения допустимого базисного реше­ ния. Теперь, используя уравнения (3.57) — (3.66) и по­ лученные численные значения неизвестных, представим переменные в следующем виде:

171

Подставив значение системы уравнений (3.67) в це­ левую функцию (3.56), получим следующее уравнение:

К = 8428 4- 2 7 , 9 х п + 29,4х12 + 28,7х33 —

В уравнении (3.68) переменными являются те самые неизвестные, которые ранее были приняты равными нулю.

Теперь имеются уже все исходные данные для со­ ставления первой спмплекс-таблпцы (табл. 39). Симп-

Т а б л и ц а 39

лекс-таблица составляется следующим образом: вверху по горизонтали записываются неизвестные, ранее приня­ тые за нуль; в столбце слева записываются неизвестные, которые были определены решением системы уравнений (3.57) — (3.66); в индексе — их численные значения; в нижней строке приведены коэффициенты уравнения

172

(3.68) с обратным знаком; таблица содержит значения коэффициентов системы уравнений (3.67) также с об­ ратным знаком.

Симплекс-таблицей пользуются следующим образом: в самой нижней строке находят максимальное положи­ тельное значение коэффициента (при максимизации це­ левой функции следует искать максимальное отрица­ тельное значение). В приведенном примере это 19,3 в столбце х4о. Затем в этом столбце берут коэффициент, деление на который коэффициентов второго столбца даст минимальное значение. В рассматриваемом приме­ ре [1,09:0,42 = 2,4; 1,65 :(—0,42); 6,5:1] таким коэффи­ циентом является 0,42, находящийся на пересечении строки л-92 и столбца х'42 (обозначен звездочкой). Назо­

вем этот коэффициент главным элементом. Затем ме­ няем местами х22 н х.І2- Таким образом, х22 принимается

за нуль в следующем базисном решении. На место быв­ шего главного элемента записываем его обратное значе­ ние (1 : 0,42 = 2,4). Остальные значения строки, содержа­ щей главный элемент, умножаем на обратное значение

(1,09-2,4 = 2,61; 0,39-2,4 = 0,93; —0,61-2,4= — 1,47 и т.д.),

а значение столбца, содержащего главный элемент, ум­ ножаем на обратное значение главного элемента, взя­ того с обратным знаком [(—0,42-2,4)-(— 1) = 1,0; (1,0Х

Х2,4) • (— 1) = —2,4 и т. д.]. Полученное значение яв­ ляется «скелетом» новой таблицы. Оставшиеся пустыми другие строки и столбцы новой симплекс-таблицы за­ полняются следующим образом. Численное значение коэффициента табл. 39 уменьшается на величину, рав­ ную произведению коэффициента, находящегося в той же строке, но в столбце главного элемента старой таб­ лицы (см. табл. 40), на коэффициент, находящийся в том же столбце, но в строке бывшего главного элемента табл. 39 и уже вписанный в эту таблицу. Например, бывшее значение коэффициента на пересечении х23 и Х[2, равное ■—0,39, в новой таблице будет иметь значение

—0,39— (0,42) -0,93 = 0.

Выполнив все необходимые вычисления, получим но­ вую симплекс-таблицу (табл. 40).

Подставив значения коэффициентов из табл. 37 в уравнение (3.68), получим коэффициенты самой нижней строки. После этого начинается новый этап вычислений, аналогичный только что выполненному, т. е. ищут мак­ симальное положительное значение коэффициента в са-

173

мой нижней строке (теперь уже) табл. 37, затем глав­ ный элемент таблицы и т. д. Когда в самой нижней строке не будет ни одного положительного значения, задача считается решенной — это и будет искомый ми­ нимум. В нашем примере минимум достигается уже на третьем шаге вычислений, и симплекс-таблица прини­ мает иной вид (табл. 41).

174

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

применяться ни первый, ни второй типы технологии, на руднике В не должен применяться второй тип, а на руд­ никах В и Г не должен применяться третий тип (с руч­ ной сортировкой в забое). Только при соблюдении ука­ занных условий может быть достигнута минимальная стоимость добычи и переработки руды на указанных четырех рудниках с применением рассмотренных трех типов технологии.

3. НЕЛИ НЕЙНО Е П Р О ГР А М М И РО В А Н И Е

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

В дальнейшем будут рассмотрены следующие задачи нелинейного программирования:

1 ) статические детерминированные нелинейные зада­

чи (в данном параграфе;)

2 ) динамические детерминированные задачи (в сле­

дующем параграфе); 3) статические стохастические задачи (гл. 4).

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

Второй метод решения задач нелинейного програм­ мирования основан на применении рекуррентных соотно­ шений Р. Веллмана [13, 55].

175