Задачи о расстановке оборудования

1. Вычислить значение функции .

2. Вычислить значения функции для x от 0 до 5 с шагом 0,5.

3. Дан массив из 7 чисел. Найти сумму положительных элементов массива.

МОДЕЛИ ЗАДАЧ ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ ГОРНЫМ ПРОИЗВОДСТВОМ

Задачи о расстановке оборудования

Задачи о расстановке оборудования возникают, когда используется разнотипное оборудование, и имеются различные по своим характеристикам участки работы. На горных предприятиях такие задачи возникают, когда необходимо расставить бригады или отдельных рабочих по местам работы; распределить транспортные средства по участкам, оборудование по блокам (уступам, забоям) и т.д.

Расстановка оборудования должна обеспечивать минимальные затраты на выполнение заданного объема работ или максимизацию выполняемого объема работ (выпуска продукции) имеющимся оборудованием. Соответственно критерием оптимальности могут служить затраты (денежные или времени) либо объем работ (выпуск продукции в натуральном или денежном выражении).

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

Имеется оборудование нескольких типов, которое можно использовать на различных участках. Количество оборудования каждого типа и его производительность на различных участках известны. Необходимо так расставить оборудование по участкам, чтобы общее время работы оборудования для выполнения заданного объема работы было минимальным.

Обозначим через i номер участка работы (i = 1, 2, ..., n); j - тип оборудования (j = 1, 2, ..., т); р_ij - производительность j-гo оборудования на i-м участке; V_i - плановый объем работы на i-м участке; К_j - количество единиц оборудования j-гo типа. За управляемые переменные можно принять х_ij - объем работы на i-м участке j-го оборудования или у_ij - время работы на i-м участке j-гo оборудования.

Приведем модели задач для обоих типов управляемых переменных, что проиллюстрирует возможность создания различных моделей для решения одной и той же задачи.

За критерий оптимальности примем общее время выполнения всего заданного объема работ. Общее время работы слагается из времени работы каждого вида оборудования j на всех участках i и выражается следующим образом:

(8)

Выражение (8) представляет собой целевую функцию задачи.

При решении задач должны соблюдаться следующие ограничения:

а) по выполнению планового объема работ на каждом участке V_j

(9)

б) по имеющемуся количеству оборудования

(10)

в) по положительности решения

(11)

Число ограничений первого типа в задаче равно n, второго m и третьего – n×m.

Модель этой же задачи с управляемыми переменными y_ij имеет следующий вид:

(12)

при ограничениях

(13)

(14)

(15)

где - число машино-часов работы оборудования j-го типа.

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

Если стоимость одного машино-часа работы оборудования различных типов существенно отличается и равна с_j,то в качестве критерия оптимальности используются суммарные затраты на выполнение заданного объема работ:

, (16)

или

(17)

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

(18)

при ограничениях:

а) по выполнению минимально необходимого объема работ на участке

(19)

б) по количеству оборудования

(20)

в) по положительности решения

(21)

В этой модели объемы работ по участкам равноценны. В ряде же случаев бывает выгоднее увеличивать объемы на отдельных участках или пропорционально перевыполнять объемы на всех участках. В этом случае модель задачи изменяется в соответствии с конкретной обстановкой. Покажем это на примерах.

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

За управляемые переменные примем объем груза, вывозимый автосамосвалами с каждого участка, x_ij, где i - номер участка (i= 1, 2, . . ., n); j - тип самосвала (j = 1, 2, …, т).

Исходными данными (неуправляемыми переменными) являются:

Q_ij - производительность j-гo типа самосвала на i-м участке;

N_j - число самосвалов j-гo типа;

v_i - отношение объемов работ i-гo участка к общему объему работ, т.e. удельный вес каждого участка в общей производительности.

Исходя из постановки задачи, в качестве критерия эффективности принимаем суммарный объем работ, который надо максимизировать. В этом случае работа транспорта будет наиболее производительной, что, в свою очередь снизит и затраты на перевозку.

Целевая функция задачи будет иметь вид

(22)

При максимизации целевой функции должны быть учтены следующие ограничения:

а) по числу имеющихся автосамосвалов

(23)

б) по соблюдению планового соотношения объемов работ между участками

(24)

или

(24а)

в) по положительности решения

(25)

Данная модель относится к классу линейных.

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

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

Обозначим через i номер уступа (группы уступов), i = 1, 2, ..., n (нумерация начинается с верхнего уступа); j - тип экскаватора (j = 1, 2, ..., т); Q_ij - производительность j-гo экскаватора на i-м участке; N_j - число экскаваторов j-гo типа.

За управляемые переменные примем объем работ j-гo экскаватора на i-м уступе, х_ij. Так как прирост вскрытых запасов непосредственно обеспечивается удалением вскрышных пород с нижних уступов, необходимо учитывать приоритет нижних уступов (увеличивающуюся ценность объемов работ на нижних уступах). Обозначим K_i - коэффициент приоритета нижних уступов; он должен существенно возрастать с увеличением номера уступа.

Тогда целевую функцию можно представить следующим образом:

(26)

При решении задачи необходимо учитывать ограничения:

по количеству оборудования

(27)

и по положительности решения

(28)

Если в задаче нет других ограничений, то ответ простой: все экскаваторы надо использовать на нижнем уступе. Однако такой ответ неверен. Между уступами существует взаимосвязь, при их отработке должна сохраняться минимально допустимая по правилам технической эксплуатации рабочая площадка. Таким образом, в модели должны быть учтены еще и технологические ограничения, по которым не допускается подработка верхних уступов нижними. Эти ограничения при параллельном подвигании уступов записываются следующим образом:

(29)

где H_i - высота i-го уступа; L_i - длина фронта работ i-гo уступа.

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

Модель даже с учетом технологических ограничений является линейной. Если фронт перемещается по вееру или криволинейно, то формализация технологических ограничений существенно усложняется.

4.2. Задачи об оптимальном использовании ресурсов (оптимальном плане выпуска продукции)

Многие предприятия и объединения горной промышленности являются комплексными и выпускают несколько видов продукции. Например, комбинаты цветной металлургии обычно выпускают концентраты нескольких металлов (или сами металлы), производственные объединения угольной промышленности добывают уголь разных марок, обширна номенклатура продукции заводов горного машиностроения. Выпуск каждого вида продукции требует определенного расхода ресурсов различных видов (финансовых, трудовых, сырья, материалов и т.д.). Каждый вид продукции имеет определенную себестоимость и отпускную цену. В условиях, когда известен максимально возможный и минимально необходимый выпуск продукции каждого вида, требуется составить наилучший план работы (выпуска продукции).

Обозначим через i - вид продукции (i = 1, 2, ..., n); j - тип ресурсов (j - 1, 2, ..., т); C_t - себестоимость производства продукции i - гo вида; Ц_i - отпускная цена продукции i-гo вида; а_ij - расход j-гo ресурса на изготовление i-й продукции; d_j - имеющееся в наличии количество j-гo ресурса; и - соответственно минимально необходимый (обязательное плановое задание) и максимально возможный (по условиям реализации) выпуск продукции i-гo вида.

За управляемые переменные задачи примем x_i -объем выпуска продукции i-гo вида. В качестве критерия оптимальности используется прибыль (объем реализации продукции), а ограничениями являются возможные пределы (минимальный и максимальный) выпуска продукции и количество ресурсов. Модель задачи имеет следующий вид:

максимизировать целевую функцию

(30)

при ограничениях:

а) по выпуску продукции

(31)

б) по расходу ресурсов

(32)

в) по положительности решения

(33)

Если в качестве критерия оптимальности принят объем реализации продукции в денежном выражении, то целевая функция будет иметь следующий вид:

(34)

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

Приведенные модели являются линейными, так как величина С_i,-принята постоянной и не зависимой от объема выпуска продукции. Если же то модель становится нелинейной.

Планирование добычных работ в режиме усреднения качества

Содержание полезных и вредных компонентов в полезном ископаемом на отдельных участках горного предприятия (шахты, карьера) может изменяться в широких пределах. Потребитель предъявляет к качеству сырья жесткие требования. Необходимо, учитывая возможности каждого участка, так составить план добычных работ, чтобы затраты на добычу были минимальны и выполнялись все требования потребителей к качеству руды.

Введем следующие обозначения:

i - номер участка добычи (i = 1, 2, . . ., n);

a_i - содержание первого компонента на i-мучастке;

b_i - содержание второго компонента;

g_i - содержание третьего (вредного) компонента;

и - максимально возможный и минимально необходимый объемы добычи на i-м участке (максимально возможный объем определяется техническими характеристиками оборудования, а минимально необходимый объем - по технологическим соображениям);

c_i - затраты на добычу руды на i-м участке;

Q_пл - плановый объем добычи руды;

a_пл - плановое содержание первого компонента, т.e. содержание этого компонента не должно строго соответствовать плановому;

b^min и b^max - минимально и максимально допустимые содержания второго компонента в руде;

g^max - максимальное содержание третьего компонента.

За управляемые переменные примем x_i - объем добычи на i-м участке.

За критерий оптимальности примем затраты на добычу. Тогда модель задачи будет иметь следующий вид:

минимизировать целевую функцию

(35)

при ограничениях:

а) по производительности каждого участка

(36)

б) по суммарному объему работ

(37)

в) по качеству руды

(38а)

(38б)

(38в)

г) по положительности решения

(39)

Данная задача является линейной, она относится к известному в исследовании операций классу задач о смеси (диете).

В качестве критерия оптимальности, кроме стоимостного, могут использоваться и другие показатели. Например:

суммарный объем добычи (при планировании в течение смены)

(40)

В этом случае второе ограничение (по объему добычи) становится лишним;

минимальное отклонение качества по основному компоненту от планового:

(41)

где

(42)

В этом случае не требуется ограничение по качеству первого (основного) компонента;

равномерный объем добычи по участкам

или (43)

где

Этот же критерий может иметь и квадратичную форму

(44)

При использовании критериев равномерности добычи или минимальных колебаний качества задача становится нелинейной

Планирование перевозок грузов горных предприятий

Грузы горной промышленности составляют значительный удельный вес (до 40%) в грузообороте страны. Поэтому рациональное планирование грузоперевозок является важной задачей и составляет большой класс задач, называемых транспортными. Эти задачи относятся к линейным.

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

Приведем модель транспортной задачи в общем виде.

Имеется n производителей (поставщиков) однородного продукта (i = 1, 2, . . ., n) и m потребителей (j == 1, 2, . . ., m). Объем груза, который необходимо вывезти от i-гo поставщика, А_i, а потребность j-гo потребителя B_j. Затраты на перевозку единицы груза от i-гo поставщика j-му потребителю составляют c_ij.

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

За управляемые переменные примем x_ij - объем груза, перевозимого от i-гo поставщика j-му потребителю.

Целевую функцию задачи можно представить в следующем виде:

(45)

Ограничениями задачи (помимо требований положительности переменных, которые здесь и в дальнейшем не указываются) являются:

а) обязательность вывоза грузов от каждого поставщика

(46)

б) полное удовлетворение запросов потребителей

(47)

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

(48)

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

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

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

Введем следующие обозначения:

i - номер забоя карьера (участка горного предприятия), i = 1, 2, ..., n;

j - номер отвала (приемного пункта), j= 1, 2, ..., m;

Q_i - объем работ по i-му участку;

Qj - максимальная приемная способность j-гo отвала;

c_ij - затраты на перевозку единицы объема из i-гo забоя в j-й отвал.

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

За управляемые переменные примем x_ij - объем грузоперевозок с i-го участка на j-й отвал, тогда целевая функция примет следующий вид:

(49)

при ограничениях

а) по объему работ по участкам

(50)

т.e. с каждого участка нужно увезти породу полностью;

б) по приемной способности отвалов

(51)

т.e. объем пород, вывозимых в отвал, не может превышать его приемной способности;

в) по положительности переменных

(52)

Модель открытая, так как есть ограничения неравенства, и приемная способность отвалов превышает объем вскрыши по карьеру

(53)

Модель задачи планирования работы группы горных предприятий (добывающих и перерабатывающих)

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

Введем следующие обозначения:

i - добывающие предприятия (i = 1, 2, .. ., n);

j - перерабатывающие предприятия (j= 1, 2, ..., m);

a_i - содержание полезного компонента на i-м предприятии;

- максимально возможный объем добычи на i-м предприятии;

c_i - затраты на добычу на i-м предприятии;

- максимальный объем переработки на j-м предприятии;

- извлечение полезного компонента в концентрат на j-м перерабатывающем предприятии из руды, добытой на i-м предприятии;

- затраты j-гo предприятия на обогащение 1 т руды, добытой на i-м предприятии;

- требуемое минимальное содержание полезного компонента на j-м предприятии;

- допустимое максимальное содержание полезного компонента на j-м предприятии;

c_ij - затраты на транспортирование руды с i-гo рудника на j-ю обогатительную фабрику;

Ц - цена единицы конечной продукции.

Управляемыми переменными в задаче являются:

y_i - плановая добыча на i-м предприятии;

y_j - плановый объем переработки на j-й обогатительной фабрике;

x_ij - объем перевозок с i-гo добывающего предприятия на j-ю обогатительную фабрику.

При этом

и (54)

В данной постановке за критерий оптимальности можно принять прибыль комбината

П = Д - З_Д - З_Т - З_О, (55)

где Д - доход комбината; З_д, З_т и З_О- соответственно затраты на добычу, транспорт и обогащение.

Целевая функция задачи имеет следующий вид:

(56)

При ограничениях:

а) по объему добычи

(57)

б) по объему переработки

(58)

в) по содержанию металла (по качеству)

(59)

В простейшем случае, когда a_i, c_i, c_ij, , и не зависят от объемов добычи, переработки и перевозок, задача является линейной. Если же эти величины являются функциями управляемых переменных, то задача существенно усложняется и становится нелинейной.