Книги по разным темам Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |

з 3. Распределительные модели 3.1. Модели распределительных процессов Задачи оптимального распределения взаимозаменяемых ресурсов получили название распределительных задач. Для их формулировки введём обозначения:

i - номер одного из взаимозаменяемых ресурсов, p - общее число взаимозаменяемых ресурсов;

ai - общее количество i-го ресурса;

k - номер потребителя, q - общее число всех потребителей;

bk - количество лединиц потребности k-того потребителя;

cik - оценка использования единицы i-го ресурса на удовлетворение k-го потребителя;

- количество лединиц потребности k-того потребителя, которые ik удовлетворяются единицей i-го ресурса;

xik - количество единиц i-го ресурса, используемых для удовлетворения k-го потребителя.

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

p q xc min(max) ik ik i=1 k=q ax i = 1,..p ik i k=(1) q bx k = 1,..q ik ik k k=(2),0 ix = 1..p,k = 1..q ik (3) В зависимости от конкретного характера задачи может варьироваться конкретное содержание, а также размерность исходных величин ai, bk, cik,, ik что в свою очередь приведёт к некоторой модификации модели. Так, например, может выражать число единиц i-го ресурса, затрачиваемых на ik единицу k-той потребности. Тогда ограничения (1), (2) заменяются на q ax ik i k =p xik bk i=ik Если при этом cik означает оценки единицы k-го изделия в руб./шт, то изменится и выражение для целевой функции:

p q xc ik ik min(max) i=1 k=ik Целевая функция может максимизироваться, например, если cik означает прибыль, стоимость и т.д., или минимизироваться, если эти оценки измеряют затраты, себестоимость и т.д. Форма модели также будет зависеть от выбора переменных xik. Вне зависимости от этих полученных модификаций модели она имеет некоторое сходство с транспортной. Однако наличие в одной из групп ограничений множителей приводит к известным ik осложнениям при анализе этих моделей.

Распределительные задачи решаются с помощью специальных вычислительных методов, представляющих собой модификацию методов решения транспортных задач. Частными видами таких задач являются:

1) простые распределительные задачи (все = const);

ik 2) задачи с однородными ресурсами (все строки матрицы ( ) одинаковы, то ik есть = при различных k);

ik 1k 3) задачи с пропорциональными ресурсами ( = при различных i).

ik i 1k 3.2. Задачи для закрепления приемов моделирования распределительных процессов Задача 1. Имеется три сорта бумаги в количествах 10, 8 и 5 т, которые можно использоватьна издание четырёх книгтиражом в 8000, 6000, 15000 и экземпляров. Расход бумаги на одну книгу составляет 0,6, 0,8, 0,4 и 0,5 кг, а себестоимость коп.) печатания книги при использовании i-го сорта бумаги (в задаётся матрицей:

24 16 32 (cC )== 18 24 24 ik 30 24 16 Определить оптимальное распределение бумажных ресурсов.

Вариант решения 1. Обозначим через xik количество бумаги i-го сорта, расходуемой на печатьk-той книги. Тогда получим следующие ограничения на запасы бумаги (по каждому сорту):

+ xx + + xx 11 12 13 + xx + x23 + x24 21 (1) + xx + x33 + x34 31 Ограничения на производственную программу:

( xx11 21 ++ x31),0 ( xx12 22 ++ x32 ),0 (2) ( xx13 23 ++ x33),0 ( xx14 24 ++ x34 ) 5, Требование неотрицательности переменных:,0 ixik =1..3,k = 1..4.

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

(24 18xx11 21 ++ 30x31)+ 6,(16 24xx12 22 ++ 24x32)+,0 (32 24xx13 23 ++ 16x33)+,0 (25 20xx14 24 ++ 20x34)+ min,0 (4) Ограничения (1-3) и целевая функция (4) составляют искомую математическую модель.

Вариант решения 2. Обозначим через xik количество экземпляров k-той книги, отпечатанной на бумаге i-того сорта. Тогда получим следующие ограничения на запасы бумаги (по каждому сорту):

,0 6 + 0,8xx11 12 + 0,4x13 + 0,5x14,0 6 + 0,8xx21 22 + 0,4x23 + 0,5x24 (1),0 6 + 0,8xx31 32 + 0,4x33 + 0,5x34 Ограничения на производственную программу:

+ xx + x31 11 + xx + x32 12 (2) + xx + x33 13 + xx + x34 14 Требование неотрицательности переменных:,0 ixik =1..3,k = 1..4.

(3) Функция цели:

24 +16xx11 12 + 32x13 + 25x14 + 18 24xx21 22 ++ 24x23 + 20x24 + 30 24xx31 32 ++ 16x33 + 20x34 min (4) Ограничения (1-3) и целевая функция (4) составляют искомую математическую модель.

Задача 2. Авиакомпания для организации пассажирских перевозок между центром и четырьмя городами располагает тремя группами самолётов: 1-я группа - из 10 четырёхмоторных самолётов, 2-я - из 25 двухмоторных самолётов и 3-я - из 40 двухмоторных старого образца.

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

человек), и связанные с этим эксплуатационные расходы на 1 самолёт (в тыс.

рублей) указаны соответственно в правых верхних и левых нижних углах каждой клетки таблицы. Там же в двух последних строках приведены:

количество пассажиров, которое нужно перевезти по данному маршруту в месяц, и стоимостьодного билета.

маршрут Город самолет 1 2 3 1,6 2,2 1,1 - 16 20 2,8 3,0 2,4 2,30 25 20 0,8 1,0 1,3 - 15 12 Количество пассажиров, 20 50 40 тыс. чел.

Стоимостьбилета, 25 15 20 руб.

Распределить самолёты по маршрутам из условия достижения максимальной прибыли авиакомпании.

Решение. Обозначим через xij количество самолетов i-го вида, выполняющих рейсы по j-му маршруту. Тогда получим ограничения на количество самолетов каждого вида:

+ xx + + xx 11 12 13 + xx + x23 + x24 21 (1) + xx + x33 + x34 31 В данной задаче потребностью является необходимость перевезти определенное количество пассажиров по определенному маршруту. Тогда ограничения на удовлетворение потребностей будут выглядеть следующим образом:

,1 6 + 2,8xx11 + 0,8x31,2 2 + 3,0xx21 22 (2),1 3 + 2,4xx31 +1,0x33 2,0 +1,5xx42 43 Требование неотрицательности переменных:,0 ixij = 1..3, j = 1..4.

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

25(1,6 + 2 8, xx11 21 + 0,8x31)+15(2,2x12 + 3x22 )+ 20(1,3x13 + 2,4x23 +1x33)+15(2x24 +1,5x34 )(16 +- 20xx +15x13)- (30x21 + 25x22 + 20x23 + 25x24 )- (15x31 +12x33 +16x34 ) max 11 (4) Ограничения (1-3) и целевая функция (4) составляют искомую математическую модель.

3.3. Задачи для самостоятельного решения 1. На четырёх ткацких станках с объёмом рабочего времени 200, 300, 250 и 400 станко-часов может изготавливаться тканьтрёх артикулов в количествах 260, 200, 340 и 500 метров за 1 час. Составитьмодельформирования плана загрузки станков, если прибыль (в руб.) от реализации 1 м ткани i-го артикула при её изготовлении на k-м станке характеризуется элементами матрицы:

5,2 2,2 2,0 2, (cC ) ==,2 2 1,0 1,9 1,2, ik,1 6 1,0 0,6 0 9, а суммарная потребностьв ткани каждого из артикулов равна соответственно 200, 100 и 150 тыс. м.

2. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 50, 70, 65 и 60 руб. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300 и 200 машин. Избыточные мощности 1-й и 2-й мастерских могут бытьиспользованы для обслуживания других видов работ, в 3-й и 4-й мастерских - только на указанный вид работ. Матрица 40 10 70 20 80 30 60 30 30 (cC ) == ik 10 40 50 20 30 10 характеризует транспортные расходы на доставку машины с i-й автобазы на k-тую ремонтную мастерскую.

Определить минимальную годовую потребность в кредитах на выполнение указанного объёма ремонтных работ по всем автобазам.

3. Четыре различных предприятия могут выпускать любой из четырёх видов продукции. Производственные мощности предприятий позволяют обеспечитьвыпуск продукции каждого вида в количествах (по заводам): 50, 70, 100 и 30 тыс. штук, а плановое задание составляет соответственно (по видам продукции) 30, 80, 20 и 100 тыс. шт. Матрица 459 75 9 (cC ) == ik 46 8 68 7 характеризует себестоимостьединицы k-го вида продукции при производстве его на i-м предприятии.

Найти оптимальное распределение планового задания между предприятиями.

4. Имеется три предприятия (1, 2, 3), которые могут выпускать три вида продукции: А, Б, В. Каждое из них располагает двумя видами ресурсов (I, II), объёмы которых составляют для 1-го предприятия 250 и 150 единиц, для 2-го 100 и 200 единиц и для 3-го соответственно 240 и 300 единиц. Известны:

нормы затрат каждого ресурса на i-м предприятии для производства единицы k-й продукции (k = 1, 2, 3); себестоимость производства единицы k-й продукции на i-м предприятии; объём производства k-й продукции, предусмотренный производственной программой.

Все указанные числовые данные приведены в следующей таблице:

Предпри- Продукция А Продукция Б Продукция В ятия Нормы затрат себесто- Нормы затрат себесто- Нормы затрат себестоI II имость I II имость I II имость ресурс ресурс ресурс ресурс ресурс ресурс 1 2 4 2 1,1 2 8 2,5 3 2 1,5 5 3 1,6 3 7 2,2 2,5 3 2,2 3 2,5 1,2 2,4 9 2,4 4,2 Программа 300 170 выпуска Составить математическую модель для определения оптимальной специализации производства из условия минимизации суммарной себестоимости.

Решить ту же задачу из предположения, что I вид ресурсов жёстко закреплён за предприятием, а II вид можно передавать от одного предприятия другому.

з 4. Моделирование процессов смешивания 4.1. Типовые модели процессов смешивания Рассматривается проблема составления смесей из различных компонент, обладающих заданным набором свойств. Среди всевозможных смесей необходимо найти смесь, обладающую заданными свойствами, согласующимися со свойствами компонент, и имеющую минимальную стоимость.

Вид формализованной модели задачи составления оптимальных смесей зависит от типов переменных. Если в качестве переменных xj взятьдолю j-й компоненты в смеси, то модель запишется в виде:

n x =j j=(1) n xa Ri i = 1,..m ij j j=(2) xa b j = 1,..n jj j (3) n xc min jj j =(4) Здесь:

i - порядковый номер свойств, которыми обладают компоненты и смесь, i =1..m;

aij - величина i-го свойства для j-той компоненты;

Ri - требование на величину i-го свойства для ед. смеси;

(,ba ) - интервал возможного включения j-той компоненты в смесь;

jj cj - стоимостьединицы j-той компоненты.

Если неизвестные сформулированы в виде: xj - объём вложений j-той компоненты в натуральном выражении, то ограничение (1) приведённой выше модели записывается в виде:

n j = bx, j=где b - общее количество смеси, которое должно быть получено.

В такие модели, как правило, также включаются ограничения (2-3).

Однако bj несёт иную смысловую нагрузку. Здесь bj - количество j-той компоненты, которое есть в наличии.

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

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

j - вид культуры, J - число всех видов культур;

i - вид смеси удобрений, I - число всех видов смесей;

q - способ внесения удобрений, Q - число всех способов внесения удобрений;

r - номер формы, в которой находится действующее вещество в удобрении (легко- или труднорастворимые);

Nr, Pr, Kr - количество азота, фосфора и калия r-й формы, имеющегося на предприятии;

Niqjr, Pijqr, Кijqr - количество действующего вещества азота, фосфора и калия rй формы, необходимого для внесения по q-му способу в i-ю смесь под j-ю культуру на 1 га земли;

m - вид органического удобрения, M - число всех видов органических удобрений;

Hm - количество m-го вида органических удобрений, имеющихся на предприятии, Hijqm - количество органического удобрения m-го вида, вносимое по q-му способу в i-ю смесь под j-ю культуру на 1га земли;

Sjq - площадь посева под j-ю культуру, в которую можно внести удобрения по q-му способу;

aijq - логический коэффициент, равный 1, если можно внести i-ю смесь q-м способом под j-ю культуру, и равный 0 в противном случае;

Cijq - эффективность (прибыль полученная при внесении i-й смеси q-м ), способом под j-ю культуру на 1га земли;

xijq - число гектаров земли, отводимое под j-ю культуру с внесением i-й смеси удобрения q-м способом.

Получим следующую математическую модель :

I J Q ijqxc ijq max i=1 j=1 q=I l Q Азотные удобрения: xN N ijqr ijq r i=1 j=1 q=I J Q Фосфорные удобрения: xP Pr ijqr ijq i=1 j=1 q=I J Q Калийные удобрения: xK K ijqr ijq r i=1 j =1 q=I J Q Органические удобрения: xH H, m = 1..M ijqm ijq m i=1 j=1 q=I Площади: xa S, j = 1..J, q = 1..Q ijq ijq jq i=,0 ix = 1..I, j = 1..J, q = 1..Q ijq 4.2. Задачи на закрепление приемов моделирования процесса смешивания Задача 1. Из четырёх видов основных материалов (медь, цинк, свинец, никель составляют три вида сплавов латуни: обычный, специальный и для ) художественных изделий. Цены единицы веса меди, цинка, свинца и никеля составляют 0,8 руб., 0,6 руб., 0,4 руб. и 1,0 руб., а единицы веса сплава, соответственно, 2 руб., 3 руб., 4 руб.

Сплав для художественных изделий должен содержать не менее 6% никеля, не менее 50% меди и не более 30% свинца; специальный - не менее 4% никеля, не менее 70% меди, не менее 10% цинка и не более 20% свинца.

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

Производственная мощность предприятия позволяет выпускать (за определённый срок) не более 400 ед. веса обычного сплава, не более 700 ед.

веса специального сплава и не более 100 ед. веса сплава для художественных изделий.

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

Решение. Обозначим через xij долю i-той компоненты в j-той смеси. Тогда получим следующие ограничения модели:

+ xx + x31 + x41 = 11 xx ++ x32 + x42 = 12 xx ++ x33 + x43 = 13 (1) Ограничения на количество компонент в смесях:

,0 ;7 xx 0, ;1 x32 0,2; x42 0,12,0 ;5 xx 0 3, ; x43 0,13 (2) Требование неотрицательности переменных:,0 ixij = 1..4, j = 1..3.

(3) Целевая функция представляет собой сумму величин прибыли, получаемой с единицы веса каждого сплава:

Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |    Книги по разным темам