2015-06-28
3940
1.2.1. Задача об использовании мощностей
Пример 7. На двух автоматических линиях выпускают аппараты 3-х типов. Условия производительности и затрат на работу приведены в табл. 7.
Таблица 7
| Тип аппарата | Производительность | Затраты на работу | План, шт | ||
| А | |||||
| В | |||||
| С |
Составить такой план загрузки линий, чтобы суммарные затраты были минимальны, а задание было бы выполнено не более, чем за 15 суток.
Решение: хij – затраты времени на изготовление i -го вида продукции на j -ой линии. Суммарные затраты на выполнение плана по производству:
Fmin = 4*400х11 + 3*300х12 + 6*100х21 + 5*200х22 + 8*300х31 +
+ 2*400х32
4х11 + 3х12 = 50 - ограничения объема продукции А,
6х21 + 5х22 = 40 - ограничения объема продукции В,
8х31 + 2х32 = 50 - ограничения объема продукции С.
Так как время работы каждого станка не превышает 15 суток, то
х11 + х21 +х31≤ 15
х12 + х22 +х32 ≤ 15.
хij ≥ 0
Пример 8. Выполнить заказ по производству 32 изделий И1 и 4 изделий И2 взялись бригады Б1 и Б2. Производительность бригады Б1 по производству изделий И1 и И2 составляет соответственно 4 и 2 изделия в час, фонд рабочего времени этой бригады 9,5 ч. Производительность бригады Б2 – соответственно 1 и 3 изделия в час, а ее фонд рабочего времени – 4 ч. Затраты, связанные с производством единицы изделия, для бригады Б1 равны соответственно 9 и 20 руб., для бригады Б2 – 15 и 30 руб.
Составьте математическую модель задачи, позволяющую найти оптимальный объем выпуска изделий, обеспечивающий минимальные затраты на выполнение заказа.
Решение: пусть x11 – количество изделий И1 и x12 – количество И2, изготавливаемых бригадой Б1; x21 – количество изделий И1 и x22 – количество изделий И2, изготавливаемых бригадой Б2. Тогда
F(X) = 9x11 + 20x12 +15x21 + 30x22 → min.
x11 + x21 = 32 - количество изделий И1, произведенных бригадами Б1 и Б2
x12 + x22 = 4 - количество изделий И2
Если известна производительность каждой бригады, т.е. количество производимых изделий в 1 ч., то трудоемкость есть обратная величина. Тогда 1/4 ч тратит бригада Б1 на производство одного изделия И1 и 1/2 ч на производство одного изделия И2; 1/1 ч тратит бригада Б2 на производство одного изделия И1 и 1/3 ч на производство одного изделия И2.
1/4x11 + 1/2x12 ≤ 9,5 - общее время, затраченное бригадой Б1 на выпуск изделий И1 и И2
1/1x21 + 1/3x22 ≤ 4 - общее время, затраченное бригадой Б2
xij ≥ 0
В общем виде: предприятию задан план производство продукции по времени и номенклатуре: требуется за время Т выпустить n1, n2, …, nk единиц продукции Р1, Р2, … Рк.. Продукция производится на станках S1, S2, …, Sm. Для любого станка известны производительность aij (число единиц продукции Pj которую можно произвести на станках Si, 
) и затраты bij на изготовление продукции Pj на станке Si в 1 единицу времени. Необходимо составить такой план работы станков хij (время, в течении которого станок Si будет занят изготовлением продукции Pj), чтобы затраты на производство всей продукции были минимальны.
ограничение работы станков - 
,
ограничения по номенклатуре - 
,
любое хij ≥ 0.
1.2.2. Перевозка грузов
Пример 9. Заводы некоторой автомобильной фирмы расположены в городах А, В и С. Основные центры распределения продукции сосредоточены в городах D и E. Объемы производства указанных трех заводов равняются 1000, 1300 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимости перевозки автомобилей по железной дороге по каждому из возможных маршрутов приведены в табл. 8.
Постройте математическую модель, позволяющую определить количество автомобилей, перевозимых из каждого завода в каждый центр распределения, таким образом, чтобы общие транспортные расходы были минимальны.
Таблица 8
Стоимость перевозки автомобилей, руб./шт.
| Заводы | Центры | |
| D | E | |
| A | ||
| B | ||
| C |
Решение. xik - количество груза, перевозимого от i поставщика к j потребителю, тогда целевая функция имеет вид:
Z = 80х11 + 215х12 + 100х21 + 108х22 + 102х31 + 68х32 à min
Мощность поставщиков: x11 + x12 =1000
x21 + x22 = 1300
x31+ x32 = 1200
Мощность потребителей: x11 + x21 + x31 =230
x12 + x22 +…+ x32 = 1400
любое хij ≥ 0
В общем виде: ai - количество груза, которое должен бы доставить потребителю (мощность поставщиков), где i = 1,p, bj - мощность потребителей (j = 1,q), q - число потребителей, p - число поставщиков. Обозначим сij - коэффициент затрат (стоимость перевозки одной единицы продукции из i пункта в j). Необходимо составить план перевозок груза (указать сколько единиц груза должно быть отправлено из i пункта в j), чтобы суммарные затраты на перевозку были наименьшими.
Пусть xij - количество груза, перевозимого от i поставщика к j потребителю, тогда целевая функция имеет вид:
Z= 
à min (4)
Начальные ограничения по ресурсам 
(5)
Начальные ограничения по потребностям 
(6)
Чтобы ТЗ ЛП имела решение необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, то есть выполняется условие:
(7)
Если отсутствует условие баланса (8), то ТЗ называется открытой. Для ее решения вводим:
- фиктивный (q+1) пункт потребления, если ∑аi > ∑bj, с объемом
bq+1 = ∑аi - ∑bj;
- фиктивный (p+1) пункт отправления, если ∑аi < ∑bj, с объемом
ap+1=∑bj - ∑ai;
Введение фиктивного потребителя или отправителя влечет необходимость формального задания фиктивных тарифов cijф (реально не существующих) для фиктивных перевозок. Поскольку нас интересует определение наиболее выгодных перевозок, то необходимо предусмотреть, чтобы при решении задачи (при нахождении опорных планов) фиктивные перевозки не рассматривались до тех пор, пока не будут определены все реальные перевозки. Для этого надо фиктивные перевозки сделать невыгодными, то есть дорогими, чтобы при поиске решения задачи их рассматривали в самую последнюю очередь. Таким образом, величина фиктивных тарифов должна превышать максимальный из реальных тарифов, используемых в модели, то есть
cijф > maxcij.(i = 1,…,n; j = 1,…,m).
На практике возможны ситуации, когда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов cijз. Запрещающие тарифы аналогично должны превышать максимальный из реальных тарифов, используемых в модели:
cijз > maxcij.(i = 1,…,n; j = 1,…,m).
Пусть требуется при решении ТЗ ограничить перевозки от поставщика l к потребителю k.
1 случай: хlk ≥ а.
Тогда, сначала необходимо уменьшить запасы поставщика l и запросы k потребителя на величину а (т.е. зарезервировать перевозку хlk = а). Затем в полученном оптимальном решении следует увеличить хlk на а.
2 случай: хlk ≤ b.
Тогда вместо потребителя k с объемом bk ввести двух потребителей bk = b и bn+1 = bk - b. Стоимости cij остаются прежними, а cl(n+1) = M (М ≥ 1). Так как cl(n+1) = M – самая максимальная стоимость, то в оптимальном решении клетка с номером (l; n+1) остается пустой (xl(n+1) = 0). Затем ищем оптимальное решении Х. Итоговый объем перевозок есть сумма объемов столбцов bk и bn+1.
Примеры 10. Дана распределительная таблица. Объем перевозок груза от второго поставщика второму потребителю должен быть не менее 200 единиц, а от третьего к первому не более 300 ед. найти оптимальное решение.
| a\b | |||
Решение. Так как х22 ≥ 200, то уменьшим запасы 2-го поставщика и 2-го потребителя на 200 ед.: а2 = 400 – 200 = 200;
b2 = 500 - 200 = 300.
Так как х31 ≤ 300, то вместо b1 = 300 и b4 = 600 – 300 = 300 со стоимостями с14 = с24= 2;с34= 100.
| a\b | ||||
Так как задача открытая, то добавим 4-го поставщика:
Решение задачи дает оптимальное решение Fmin = 5600, где
| Хопт = | ||||
Увеличим х22 на 200 и объединим объем перевозок 1-го и
4-го потребителя. Тогда Fmin = 7800
| Хопт = | |||
.
1.2.3. Задача о назначениях
В общем виде: рассмотрим задачу формирования трудового коллектива. На коммерческом предприятии имеется n работников: A1, A2,…,Am, каждый из которых должен выполнять одну Bj из имеющихся m видов работ: B1, B2,..., Вm. Для каждого работника Аi на рабочем месте Bj рассчитывается производительность труда cij. Необходимо определить, кого и на какую работу следует назначить, чтобы добиться максимальной или минимальной стоимости назначения суммарной производительности при условии, что каждый работник может быть назначен только на одну работу.
Обозначим xij назначение i -го работника на j- ю работу, которое может принимать только два целочисленных значения: 1, если i -й работник назначен на выполнение j -й работы; 0, если не назначен. Необходимо построить квадратную матрицу распределения по должностям X, которая обеспечивает экстремальное значение производительности или стоимость назначения:
Z= 
àmin
при ограничении 
Задача о назначениях является частным случаем транспортной задачи.
1.2.4. Построение кольцевых маршрутов
В общем виде: пусть расстояния между любой парой множества из n городов равно aij (i = 1,…, m; j = 1,…, n, i ≠ j). Если прямого маршрута между городами i и j не существует, то допускают, что aij = ∞. Коммерсант, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы наименьшей.
Обозначим xij = 1, если коммивояжер переезжает из города i в город j; в противном случае xij =0. Задача заключается в определении матрицы целых неотрицательных значений переменных xij, минимизирующих целевую функцию вида
Z= 
àmin
при ограничениях для въезда в город j только один раз:
для выезда из города i только один раз: 
1.2.5. Общая распределительная задача
Исходные параметры модели задачи распределения (РЗ):
1) n – количество исполнителей;
2) m – количество видов выполняемых работ;
3) ai – запас рабочего ресурса исполнителя Ai (i = 1, n)
[ед. ресурса];
4) bj – план по выполнению работы Bj (j = 1, m) [ед. работ];
5) cij – стоимость выполнения работы Bj исполнителем Ai
[руб./ед. работ];
6) λij – интенсивность выполнения работы Bj исполнителем Ai
[ед. работ / ед. ресурса];
Искомые параметры модели РЗ:
1) xij – планируемая загрузка исполнителя Ai при выполнении работ Bj [ед. ресурса];
2) xijк = (λij*xij) – это количество работ j- го вида, выполненных i -м исполнителем.
3) L(X) – общие расходы на выполнение всего запланированного объема работ [руб.].
Распределительная матрица имеет вид:
| Исполнители, Ai | Работы, Bj | Запас ресурса, ед. ресурса | |||
| B1 | B2 | … | Bm | ||
| A1 | λ11 c11 | λ11 c11 | λ1m c1m | a1 | |
| … | |||||
| An | λn1 cn1 | λn2 cn2 | λnm cnm | an | |
| План работы | b1 | b2 | bm |
Модель РЗ: L (X) = ∑∑ сij xijк → min
∑xij = ai, i = 1,n
∑ xijк = bj, j = 1,m
xij ≥ 0.
Этапы решения РЗ.
I. Преобразование РЗ в ТЗ:
1) выбор базового ресурса и расчет нормированных производительностей ресурсов αij = λij/ λбаз j;
2) пересчет запаса рабочего ресурса исполнителей
a′i = αi*ai [ед. ресурса];
3) пересчет планового задания b′j = bj / λбаз j [ед. ресурса];
4) пересчет себестоимостей работ:
с′j = сj * λбаз j [руб/ед. ресурса];
II. Определение оптимального решения ТЗ.
1) проверка баланса пересчитанных параметров ΣΣa′i = ΣΣb′j и построение транспортной матрицы.
2) поиск оптимального решения ТЗ X'* = x'ij.
III. Преобразование оптимального решения ТЗ X'* в оптимальное решение РЗ X* по формуле
xij = x'ij/ αi [ед. ресурса].
IV. Определение количества работ Xк*= (xijk), соответствующее оптимальному решению РЗ X*:
xkij = λij*xij [ед. ресурса].
VI. Определение ЦФ распределительной задачи L(X*).
Пример 11. На фабрике эксплуатируются три типа ткацких станков, которые могут выпускать четыре вида тканей. Известны следующие данные о производственном процессе:
- производительности станков по каждому виду ткани, м/ч
| 24 | 30 | 18 | 42 | |
| λij = | 12 | 15 | 9 | 21 |
| 8 | 10 | 6 | 14 |
- себестоимость тканей, руб./
| 2 | 1 | 3 | 1 | |
| сij = | 3 | 2 | 4 | 1 |
| 6 | 3 | 5 | 2 |
- фонды рабочего времени станков (ai): 90, 220, 180 ч;
- планируемый объем выпуска тканей (bj): 1200, 900, 1800, 840 м.
Требуется распределить выпуск ткани по станкам с целью минимизации общей себестоимости производства ткани.
Решение. Составим распределительную таблицу 9.
Таблица 9.
| Исполнители, Ai | Работы, Bj | Фонд времени | |||
| B1 | B2 | B3 | B4 | ||
| A1 | 2 (c11) 24 (λ11) | ||||
| A2 | |||||
| A3 | |||||
| Объем выпуска |
Общая себестоимость составит:
L(X) = 2*24*x11 + 1*30*x12 + 3*13*x13 + 1*42*x14 + 3*12*x21 +
+ 2*15*x22 + 4*9*x23 + 1*21*x24 + 6*8*x31 + 3*10*x32 + 5*6*x33 +
+ 2*14*x34 = 48*x11 + 30*x12 + 54*x13 + 42*x14 + 36*x21 + 30*x22 +
+ 36*x23 + 21*x24 + 48*x31 + 30*x32 + 30*x33 + 28*x34.
Ограничения имеют вид по фондам времени, ч:
х11 + х12 + х13 + х14 = 90
х21 + х22 + х23 + х24 = 220
х31 + х32 + х33 + х34 = 180;
по объемам выпуска, м:
24х11 + 12х21 + 8х31 = 1200
30х12 + 15х22 + 10х32 = 900
18х13 + 9х23 + 6х33 = 1800
42х14 + 21х24 + 14х34 = 84.
xij ≥ 0
Выберем базовый ресурс λ1, тогда
α1 = 24/24 = 30/30 == 18/18 = 42/42 = 1;
α2 = 12/24 = 15/30 = 9/18 = 21/42 = 1/2;
α3 = 8/24 = 10/30 = 6/18 = 14/42 = 1/3.
Пересчитаем фонды времени станков:
a′1= 1*90 = 90 ч;a′2= 1/2*220 = 110 ч; a′3= 1/3*180 = 60 ч. Из этих величин следует, что тот объем работ, который второй станок выполняет за свой фонд времени 220 ч, базовый станок сможет выполнить за 110 ч. Аналогично объем работ, который третий станок выполняет за 180 ч, базовый выполнит за 60 ч.
Пересчитаем плановое задание:
b′1 = 1200/24 = 50 ч;b′2 = 900/30 = 30 ч; b′3 = 1800/18 = 100 ч;
b′4 = 840/42 = 20 ч. Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит за 50 ч, второго вида – за 30 ч и т.д.
Пересчитаем себестоимость:
| 144 | 90 | 90 | 84 | |
| с′ij = | 72 | 60 | 72 | 42 |
| 48 | 30 | 54 | 42 |
Получим транспортную задачу:
| B1 | B2 | B3 | B4 | Фиктивный | Фонд времени a′i, ч | |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Объем выпуска b′j, ч |
В результате решения получим оптимальное решение
| 50 | 30 | 10 | 0 | 0 | |
| Х′опт = | 0 | 0 | 90 | 20 | 0 |
| 0 | 0 | 0 | 0 | 60 |
Преобразуем опорный план ТЗ X′ в опорный план РЗ
| 50 | 30 | 10 | 0 | 0 | |
| Х′ = | 0 | 0 | 180 | 40 | 0 |
| 0 | 0 | 0 | 0 | 180 |
Таким образом, первый станок должен 50 ч производить ткань первого вида, 30 ч – ткань второго вида и 10 ч – ткань третьего вида. Второй станок должен 180 ч производить ткань третьего вида и 40 ч – ткань четвертого вида. А третий станок будет простаивать, не выпуская ткань вообще, т.к. согласно решению, его загрузка находится в фиктивном столбце (x35 = 180). Определим, сколько метров ткани каждого вида должны произвести станки:
| 1200 | 900 | 180 | 0 | |
| Х к = | 0 | 0 | 1620 | 840 |
| 0 | 0 | 0 | 0 |
Итак, общая себестоимость производства составит:
L (X) = 2*1200 + 1*900 + 3*180 + 4*1620 +1*840 = 16020 (руб.).
