Распределение ресурсов
Пусть имеется m видов ресурсов, каждый i-й ресурс в количестве b (i = 1... m). Эти ресурсы нужно использовать для n видов продукции. Для выпуска единицы j-го вида продукции необходимо а^ единиц i-го вида ресурса. Требуется определить, сколько каждого вида продукции следует произвести, чтобы такой выпуск был наилучшим для принятого критерия оптимальности.
В реальных задачах суммарное количество основных %¦ ( j = 1... n) и дополнительных yi (i = 1... m) переменных всегда больше, чем число зависимостей m, поэтому система (1) ограничений имеет бесчисленное множество решений. Из этого бесчисленного множества следует выбрать одно — оптимальное, соответствующее критерию — цели решения задачи.
Цель задачи распределения ресурсов определяется какой-либо одной из двух взаимоисключающих постановок:
1. При заданных ресурсах максимизировать получаемый результат.
2. При заданном результате минимизировать потребные ресурсы.
(7.1)
(7.2)
(7.3)
Первая постановка аналитически будет сформулирована следующим образом:
max L = Yc,.x,.;
^ j j
j=1
n
"Laijxi < bi (i =1... m);
j=1
dj < Xj < Dj (j = 1... n),
J
где Xj — количество выпускаемой продукции j-го вида — искомая переменная (j = = 1 ... n); n — количество наименований продукции; c — величина, показывающая, какой вклад в результат дает единица продукции j-го вида; bi — заданное количество ресурса i-го вида (i = 1... m); m — количество наименований ресурсов; а^ — норма расхода ресурса, т. е. количество ресурса i-го вида, потребляемого на производство единицы j-го вида продукции.
Решение задачи (1) дает нахождение таких значений x, которые обеспечивают при заданных ресурсах получение максимального результата.
(7.4)
(7.5)
(7.6)
Вторая постановка задачи будет иметь вид:
min L=YLavxj;
i=1 j=1
n
Xjj > C;
j=1
dj < xj < Dj (j = 1... n),
J
где C — минимально допустимое значение потребного результата.
Совместимость ограничивающих условий
В общую постановку задачи оптимизации входят неравенства вида
n
Yajxj < b{ (i = 1... m),
j=1
где n — число неизвестных; m — число неравенств.
Если в каждое неравенство добавить неотрицательное неизвестное y > 0 (i = = 1... m), то от системы неравенств можно перейти к системе уравнений
n
Yajxj + y{ = bi (i = 1... m).
j=1
В этой системе общее число неизвестных N = n + m, где n — число основных неизвестных x; m — число дополнительных неизвестных yi, которое равно числу уравнений.
Возможны три варианта соотношения величин N и m.
1. Число неизвестных меньше, чем число уравнений: N < m.
Например, N = 1, m = 2.
Очевидно, эта система решения не имеет, т. е. нет таких значений x1, которые бы удовлетворяли обоим уравнениям. В этом случае говорят, что система условий несовместна. Значит, если число неизвестных N меньше числа уравнений m, то система решения не имеет и является несовместной.
2. Число неизвестных равно числу уравнений: N = m.
Например, нетрудно вычислить, что решением этой системы будут значения x1 = 2, x2 = 1. Таким образом, линейная система, в которой число неизвестных N равно числу уравнений m, имеет одно решение.
3. Число неизвестных больше числа уравнений: N > m.
Например, 2xt + x2 = 2. Очевидно, что все значения x1 и x2, лежащие на прямой этого уравнения, являются его решением. Если в системе число неизвестных N больше числа уравнений m, то такая система имеет бесчисленное множество решений.
7.6. Формирование производственной программы
Рассмотрим производственный участок, выпускающий два типа деталей. Исходная заготовка при изготовлении деталей первого типа проходит две операции (токарную и сверлильную) при трудоемкости 20 и 30 ч/шт. соответственно. При изготовлении детали второго типа необходимы три операции (токарная, сверлильная, шлифовальная) при трудоемкости 40, 30, 20 ч/шт. соответственно. Прибыль от продажи деталей равна 1,5 руб./шт. для деталей первого типа и 1 руб./шт. для деталей второго типа.
На плановый период ресурс рабочего времени по операциям в часах составляет: токарная — 1000, сверлильная — 900, шлифовальная — 400 ч. Необходимо подобрать производственную программу выпуска деталей, обеспечивающую максимальную прибыль.
Обозначим количество деталей первого типа, принимаемых для выпуска, через у, второго типа — х. Математическая постановка задачи определения у и х имеет вид
40 х + 20 у = 1000; 30 х + 30 у = 900; 20 х = 400; х > 0, у > 0; J = 1,5 у + 1 x ^ max.
Похожие рефераты:
