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

Таблица 4.Издержки производства и максимальный урожай бобов Издержки производства, руб./т Максимальный урожай, т 1 90 Фермы 2 95 3 87 Прогнозный спрос, т 1 20 Заводы 2 23 Таблица 4.Стоимость транспортировки бобов, руб. / т Холодильный завод Фермы 1 1 10 2 12 3 Постройте транспортную модель, которая для ферм и холодильных заводов позволяет найти на следующий сезон производственный план, гарантирующий максимальный доход.

Задача №4.5* (многопродуктовая модель с независимыми продуктами) Некоторая фирма производит автомобили четырех различных марок M1, M2, M3, M4. Завод в городе A производит только автомобили марок M3, M4, в городе B - только автомобили марок M1, M2, M4, а в городе C - только автомобили марок M1, M2. Ежеквартальные объемы выпуска каждого завода и величины спроса в каждом пункте распределения приведены в табл. 4.7.

Постройте соответствующую модель экономичных перевозок. Тарифы перевозок соответствуют задаче № 4.01.

Таблица 4.Объемы производства заводов и спроса пунктов распределения автомобилей, шт./квартал Марка автомобиля M1 M2 M3 MЗаводы А Ц - 700 B 500 600 - C800 400 - - Пункты распределения D 700 500 500 E 600 500 200 Рекомендация. Пункты отправления в транспортной матрице необходимо вводить в соответствии с марками автомобилей, выпускаемыми каждым заводом, а пункты назначения - в соответствии с марками автомобилей, требуемыми в каждом пункте распределения.

Задача № 4.6* (многопродуктовая модель с зависимыми продуктами) Исходное условие задачи № 4.5 при условии, что некоторую часть спроса на одну из марок можно удовлетворять за счет другой в соответствии с табл.

4.8. Постройте соответствующую модель экономичных перевозок.

Таблица 4.Данные о заменяемых марках автомобилей Центр Заменяемая часть спроса в % Взаимозаменяемые марки распределения 10 M1, MD 20 M3, M10 M1, ME 5 M2, MРекомендация. Введите четыре новых пункта назначения, соответствующих комбинациям (M1 или M2 ), ( M3 или M4 ), ( M1 или M2 ) и ( M2 или M4) (см. табл. 4.8). Величины потребностей новых пунктов назначения определяются на основании данных о процентном соотношении заменяемых моделей автомобилей.

Задача № 4.В цехе некоторого завода стоит пять станков, а количество рабочих в цехе равно четырем. Рабочий 1 не может работать на станке 3, а рабочий 3 - на станке 4. В соответствии с квалификацией рабочих начальник цеха в баллах оценил эффективность работы каждого из рабочих на каждом из станков (в 10бальной шкале) (см. табл. 4.9). Постройте модель, позволяющую выполнять работы на станках наилучшим образом.

Таблица 4.Бальные оценки эффективности работы рабочих на станках Станок 1 234 1 55Ц2 2 7423 Рабочий 3 935 - 4 7267 Задача № 4.8* (модель производства с запасами) Некоторая фабрика производит рюкзаки для путешественников. Спрос на эту продукцию есть только в мартеЦиюне и составляет помесячно 100, 200, и 300 шт. Объем производства рюкзаков меняется от месяца к месяцу в зависимости от выпуска других изделий. В течение рассматриваемых четырех месяцев фабрика может выпустить 50, 180, 280 и 270 рюкзаков соответственно.

В каждый месяц спрос можно удовлетворить за счет 1) производства рюкзаков в течение текущего месяца;

2) избытка рюкзаков, произведенных в прошлом месяце;

3) избытка рюкзаков, произведенных в следующем месяце в счет невыполненных заказов.

В первом случае стоимость одного рюкзака составляет 700 руб. Во втором случае возникают дополнительные расходы в расчете 10 руб. на один рюкзак за хранение в течение месяца. В третьем случае за просроченные заказы начисляются штрафы в размере 40 руб. на один рюкзак за каждый просроченный месяц.

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

Рекомендация. Чтобы производственную задачу сформулировать как транспортную, необходимо установить соответствие между элементами этих задач (табл. 4.10).

Таблица 4.Соответствие между элементами задачи № 4.Транспортная система Производственная система 1. Пункт отправления i 1. Период производства i 2. Пункт назначения j 2. Период потребления j 3. Предложение в пункте 3. Объем производства за период i отправления i 4. Спрос в пункте назначения j 4. Реализация за период j 5. Стоимость единицы продукции 5. Стоимость перевозки из i в j (производство + хранение + штрафы за период от i до j) 5. МЕТОДЫ НАХОЖДЕНИЯ ОПОРНЫХ ПЛАНОВ 5.1. Теоретическое введение Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается:

в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла - наихудшее.

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

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

Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий тек запас товара в рассматриваемой i-й строке ai с текущей потребностью в рассматриваемом j-м столбце bтек.

j Если существующий запас позволяет перевезти всю потребность, то Х в клетку (i,j) в качестве перевозки вписывается значение потребности bтек ;

j Х j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

Х от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, тек т.е. (ai - bтек).

j Если существующий запас не позволяет перевезти всю потребность, то тек Х в клетку (i,j) в качестве перевозки вписывается значение запаса ai ;

Х i-я строка вычеркивается, поскольку ее запас уже исчерпан;

Х от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее тек записывается остаток, т.е.(bтек - ai ).

j Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

Метод минимального элемента На каждом шаге метода минимального элемента из всех не вычеркнутых клеток транспортной матрицы выбирается клетка с минимальной стоимостью перевозки min cij. Заполнение выбранной клетки производится по правилам, описанным выше.

Метод Фогеля На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы di как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы d для каждого j-го столбца. После чего j выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом min cij.

Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом min cij.

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

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

Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [cф > max cij (i = 1,n; j = 1,m)], то методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами.

Задача № 5.Найти тремя методами опорный план ТЗ, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие:

5 8 1 2 5 4 9.

9 2 3 Решение Проверка сбалансированности задачи показывает, что суммарный объем запасов равен суммарному объему потребностей, т.е. введение фиктивных столбцов или строк не потребуется потребности запасы 210 +170 + 65 = 125 + 90 +130 +100.

445 ед.товара 445 ед.товара Результаты нахождения опорного плана различными методами представлены в табл. 5.1, 5.2 и 5.3.

Таблица 5.Транспортная таблица с опорным планом северо-западного угла Пункты потребления, Bj Пункты Запасы, отправления, Ai Вед. продукции В2 B3 B125 А210/85/5 8 1 5 130 A170/165/35/2 5 4 A65/Потребность, 125/0 90/5/0 130/0 100/65/ед. продукции Опорный план XСЗУ, найденный методом северо-западного угла 125 85 0 XСЗУ = 0 5 130 35 [ед. товара].

0 0 0 Соответствующая ЦФ (общие затраты на перевозку) L (X )=125 5 + 85 8 + 5 5 + 130 4 + 35 9 + 65 1 = 2230 [руб.].

СЗУ Таблица 5.Транспортная таблица с опорным планом минимального элемента Пункты потребления, Bj Пункты Запасы, отправления, Ai Вед. продукции В2 B3 B45 130 А210/80/45/5 8 1 125 A170/45/2 A65/Потребность, 125/0 90/45/0 130/0 100/35/ед. продукции Опорный план XМЭ, найденный методом минимального элемента 0 45 130 XМЭ = [ед. товара], L(XМЭ )= 1100 [руб.].

125 45 0 0 0 0 Таблица 5.Транспортная таблица с опорным планом Фогеля В1 В2 B3 B4 Штрафы строк,di bi 110 А210/110/0 1 1 581 125 25 A170/45/25/0 2 1 1 2 5 A65/0 1 1 - - 9 90/25/ 130/a 125/0 100/j 0 /Штрафы - 2 столбцов, d j 33 - На первом шаге нахождения опорного плана методом Фогеля возникает ситуация равенства значений максимальных штрафов транспортной матрицы (см. табл. 5.3) d = d = 3.

1столбца 2столбца Минимальные тарифы в этих столбцах также совпадают с21 = с32 = 2.

Поэтому необходимо сравнить суммарные штрафы dij клеток (2,1) и (3,2) d = d + d = 2 + 3 = 5;

21 2строки 1столбца d = d + d =1 + 3 = 4.

32 3строки 2столбца Т.к. d21 > d32, то выбираем на первом шаге для заполнения клетку (2,1).

Опорный план XФ, найденный методом Фогеля 0 0 110 XФ = [ед. товара], L(XФ )= 895 [руб.].

125 25 20 0 65 0 5.3. Варианты задач для самостоятельного решения Задача № 5.Найти тремя методами опорный план транспортной задачи, в которой запасы на трех складах равны 160, 140, 170 ед. продукции, потребности четырех магазинов равны 120, 50, 200, 110 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие 7 8 1 4 5 9 8.

9 2 3 Решите задачу для следующих случаев:

Х фиктивные тарифы нулевые;

Х фиктивные тарифы одинаковы по величине и превышают максимальный из реальных тарифов.

Сравните полученные опорные планы, соответствующие ЦФ и объясните причину их различия.

Задача № 5.Найти тремя методами опорный план транспортной задачи № 4.1 для случая, когда фиктивные тарифы больше максимального реального тарифа.

Задача № 5.Найти тремя методами опорный план транспортной задачи № 4.2 для случая, когда фиктивные тарифы больше максимального реального тарифа.

Задача № 5.Найти тремя методами опорный план транспортной задачи № 4.3 для случая, когда фиктивные тарифы больше максимального реального тарифа.

Задача № 5.Найти тремя методами опорный план транспортной задачи № 4.4 для случая, когда фиктивные тарифы больше максимального реального тарифа.

6. ОБЩАЯ РАСПРЕДЕЛИТЕЛЬНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 6.1. Теоретическое введение Общая распределительная задача ЛП - это РЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения.

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

Исходные параметры модели РЗ 1) n - количество исполнителей;

2) m - количество видов выполняемых работ;

3) ai - запас рабочего ресурса исполнителя Ai (i =1,n ) [ед. ресурса];

4) b - план по выполнению работы Bj ( j =1,m ) [ед. работ];

j 5) cij - стоимость выполнения работы Bj исполнителем Ai [руб./ед. работ];

6) ij - интенсивность выполнения работы Bj исполнителем Ai [ед. работ / ед. ресурса].

Искомые параметры модели РЗ 1) xij - планируемая загрузка исполнителя Ai при выполнении работ Bj [ед. ресурса];

к 2) xij - количество работ Bj, которые должен будет произвести исполнитель Ai [ед. работ];

3) L(X) - общие расходы на выполнение всего запланированного объема работ [руб.].

Этапы построения модели I. Определение переменных.

II. Построение распределительной матрицы (см. табл. 6.1).

III. Задание ЦФ.

IV. Задание ограничений.

Таблица 6.Общий вид распределительной матрицы Работы, Bj Запас ресурса, Исполнители, Ai ед. ресурса В1 В2 Bm Е 11 12 1m А1 aЕ c11 c12 c1m 21 22 2m А2 aЕ c21 c22 c2m ЕЕ Е Е Е Е n1 n2 nm An an Е cn1 cn2 cnm b1 b2 bm План, ед. работы Е Модель РЗ n m L(X)= сij(ijxij) min ;

i = 1 j = m x = ai, i = 1,n, ij j=(6.1) n xij = b, j = 1,m, ij j i=x 0 (i = 1,n; j = 1,m), ij где (ijxij) - это количество работ j-го вида, выполненных i-м исполнителем.

Этапы решения РЗ I. Преобразование РЗ в ТЗ:

1) выбор базового ресурса и расчет нормированных производительностей ресурсов i :

ij i = ;

(6.2) баз j 2) пересчет запаса рабочего ресурса исполнителей ai :

ai = iai [ед. ресурса];

(6.3) j 3) пересчет планового задания b :

b j j ед.работ ед. ресурса b = = ед. ресурса ;

(6.4) баз j ед. работ 4) пересчет себестоимостей работ:

руб. ед.работ руб.

.

cij = cijбаз j (6.5) ед. работ ед. ресурса = ед. ресурса n m II. Проверка баланса пересчитанных параметров = a b и i j i=1 j=построение транспортной матрицы.

III. Поиск оптимального решения ТЗ X'* =(x'*).

ij IV. Преобразование оптимального решения ТЗ X'* в оптимальное решение РЗ X*, причем переход X'* X* выполняется по формуле (6.6) ' xij (6.6) xij = [ед. ресурса], i ' где xij и xij - соответственно элементы решения РЗ и ТЗ.

к V. Определение количества работ Xк* =(xij*), соответствующее оптимальному решению РЗ X*:

ед. работ ед. ресурса к xij = ijxij = ед. работ.

(6.7) ед. ресурса VI. Определение ЦФ распределительной задачи L( X*) согласно (6.1).

6.2. Методические рекомендации Задача № 6.На фабрике эксплуатируются три типа ткацких станков, которые могут выпускать четыре вида тканей. Известны следующие данные о производственном процессе:

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