Классификация задач оптимизации

ЗАДАЧА О ПЛАНИРОВАНИИ ПРОИЗВОДСТВА

Постановка задачи

o Предприятие химической промышленности производит продукцию видов: П₁, П₂,..,П_j. (j= 1, 2,.., m)

o На изготовление продукции идут разные типы сырья: S₁, S₂,.., S_i.(i= 1, 2,.., n)

o Запасы ограничены числами g₁, g₂,.., g_i единиц каждого вида сырья.

o a_ij количество единиц i-го сырья, необходимое на изготовление одной единицы j-й продукции

o При реализации продукция П_j приносит предприятию прибыль m_j

o По каждому виду продукции дан план выпуска продукции: не менее b_j единиц продукции П_j

o Количество произведённых единиц каждого типа продукции ограничено условиями спроса: не более y_j единиц.

 

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

 

Математическая модель

 

Обозначения

X₁, X₂,.., X_j – количества единиц продукции П₁, П₂,..,П_j, которые может произвести предприятие.

Ограничения

Выполнение планового задания:

…

Отсутствие излишней продукции:

…

Количество сырья с учетом запасов:

 

Неотрицательность переменных

X₁, X₂,.., X_j

Целевая функция

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

 

ЗАДАЧА О СОСТАВЛЕНИИ СМЕСЕЙ

 

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

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

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

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

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

Задача смешивания может быть рассмотрена в натуральных единицах или в долях.

 

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

Постановка задачи

 

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

 

Математическая модель

Обозначения

X_jk – количество j-го вида исходного нефтепродукта, направляемое на получение k- го вида бензина

B_k – плановое задание по выпуску бензина k-го сорта,

- ограниченное количество j-го вида исходного нефтепродукта;

h_ij – содержание i – той качественной характеристики в единице j – го исходного нефтепродукта;

H_ik – содержание i - той качественной характеристики в бензине k- го вида;

C_j – цена исходного j- го нефтепродукта;

m_k– цена бензина k - го вида.

 

j= 1,2,.., n – количество исходных нефтепродуктов;

k= 1,2,.., K – количество выпускаемых бензинов;

i= 1,2,.., m – количество анализируемых качественных характеристик;

Ограничения

по объему ресурсов:

по выпуску продукции:

 

по качественным характеристикам:

 

Неотрицательность переменных

Целевая функция

Требуется определить – количество j–го вида исходного нефтепродукта, направляемое на получение k- го вида бензина.

Модель задачи представлена в выражениях:

 

4.1.3 ЗАДАЧА ОБ ИСПОЛЬЗОВАНИИ МОЩНОСТЕЙ ("О ЗАГРУЗКЕ ОБОРУДОВАНИЯ")

j= 1,2,.., n – количество исходных нефтепродуктов;

k= 1,2,.., K – количество выпускаемых бензинов;

i= 1,2,.., m – количество анализируемых качественных характеристик;

 

Пусть завод располагает двумя видами станков, соответственно и штук каждого вида. Каждый из станков может производить 3 вида деталей с производительностью

 

Каждая партия деталей(по их видам) приносит доход, соответственно, , и .

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

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

Формальная постановка задачи.

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

Математическая модель

Так как видов станков 2, а видов деталей 3, то удобнее элементы решения обозначить двумя индексами (первый - вид станка, второй - вид деталей): , , , , ,

Выполнение планового задания:

Отсутствие излишней продукции:

 

 

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

 

Суммарное количество партий деталей первого вида, произведенное всеми станками, будет равно и принесет доход ).

 

Суммарный для завода месячный доход равен:

)

 

 

Целевая функция

найти такие неотрицательные значения переменных х₁₁, х₁₂, х₁₃, x₂₁, x₂₂, x₂₃, которые должны удовлетворять ограничениям и одновременно обращали в максимум линейную функцию этих переменных, т.е.

 

Математическая модель представляет собой (4) и систему ограничений (1, 2, 3).

4.1.4 ЗАДАЧА "О ПОСТАВКЕ СЫРЬЯ"

 

№ предприятия	Склад № 1	Склад № 2	Склад № 3	Склад № 4	Склад № 5
	с11 с21 с31	с12 с22 с32	с13 с23 с33	с14 с24 с34	с15 с25 с35

 

 

Пусть имеются 3 предприятия, требующих, соответственно, а₁, а₂ и а₃ единиц сырья. Имеются 5 складов сырья, обеспечивающих стоимости поставок сырья, указанные в таблице.

 

Запас сырья на базах равен, соответственно, b₁, b₂, b₃, b₄ и b₅ единиц сырья.

 

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

 

Формальная постановка задачи. Обозначим через x_ij количество сырья, получаемое i -м предприятием с j -го склада. Всего план будет состоять из 15 элементов решения:

 

x₁₁, x₁₂, x₁₃, x₁₄, x₁₅, x₂₁, x₂₂, x₂₃, x₂₄, x₂₅, x₃₁, x₃₂, x₃₃, x₃₄, x₃₅.

 

Ограничения-равенства по потребностям:

 

Ограничения-неравенства, вытекающие из возможностей складов:

 

 

x₁₄ + x₂₄ + x₃₄ ≤ b₄;

x₁₅ + x₂₅ + x₃₅ ≤ b₅.

 

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

_{3 5}

L =∑ ∑(с_ij·x_ij) → min. (7)

^{i=1 j=1}

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