Экон. мат. моделирование
.pdf
|
|
Имеются два вида корма – I |
и II, |
содержащие витамины S1, S2 и S3. |
||||||||
|
|
Содержание витаминов в 1 кг каждого вида корма и их необходимый |
||||||||||
|
|
минимум приведены в таблице (цифры условные). |
|
|
|
|
||||||
|
|
|
Витамины |
Необходимый |
|
|
Объем витаминов в 1 кг корма, ед. |
|
||||
|
|
|
|
минимум, ед. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
|
|
II |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
S1 |
9 |
|
|
|
3 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S2 |
8 |
|
|
|
1 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S3 |
12 |
|
|
|
1 |
|
|
6 |
|
|
|
|
|
|
|
|
||||||
|
|
Стоимость 1 кг корма I и II – 4 и 6 руб. соответственно. Составить |
||||||||||
|
|
минимальный по стоимости дневной рацион, в котором содержание |
||||||||||
|
|
каждого вида питательных веществ было бы не менее установленного |
||||||||||
|
|
предела. |
|
|
|
|
|
|
|
|
|
|
|
|
Для производства двух видов изделий А и В предприятие использует три |
||||||||||
|
|
вида сырья. Другие условия задачи приведены в таблице. Составить план |
||||||||||
|
|
выпуска продукции, при котором прибыль предприятия от реализации |
||||||||||
|
|
продукции будет максимальной при условии, что изделий В надо выпустить |
||||||||||
|
|
не меньше, чем изделий А. Прибыль от реализации одного изделия А |
||||||||||
|
|
составляет 30 руб., изделия В – 40 руб. |
|
|
|
|
|
|||||
4 |
|
|
Вид сырья |
Расход сырья на 1 изд., кг |
|
Общее |
|
|||||
|
|
|
|
|
|
|
|
|
|
количество |
|
|
|
|
|
|
А |
|
|
|
В |
|
|
||
|
|
|
|
|
|
|
|
сырья, кг |
|
|||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
12 |
|
|
|
4 |
|
|
300 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
II |
4 |
|
|
|
4 |
|
|
120 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
III |
3 |
|
|
|
12 |
|
|
252 |
|
|
|
|
|
|
|
|
|
|||||
|
|
При изготовлении изделий И1 и И2 |
используются сталь и цветные металлы, |
|||||||||
|
|
а также токарные и фрезерные станки. Согласно технологическим нормам |
||||||||||
|
|
на производство единицы изделия И1 требуется 300 станко-часов токарного |
||||||||||
|
|
и 200 станко-часов фрезерного оборудования, а также 10 кг стали и 20 кг |
||||||||||
|
|
цветных металлов. Для производства единицы изделия И2 |
требуется |
|||||||||
|
|
соответственно 400, 100, 70 и 50 единиц тех же ресурсов. Цех располагает |
||||||||||
5 |
|
12400 станко-часами токарного |
и |
6800 станко-часами |
фрезерного |
|||||||
|
оборудования, 640 кг стали и 840 кг цветных металлов. Прибыль от |
|||||||||||
|
|
|||||||||||
|
|
реализации единицы изделия И1 |
составляет 6 руб., от единицы изделия И2 – |
|||||||||
|
|
16 |
руб. Составить план производства изделий И1 |
и И2 с максимальной |
||||||||
|
|
прибылью, учитывая, что время работы фрезерных станков должно быть |
||||||||||
|
|
использовано полностью. |
|
|
|
|
|
|
|
|
||
31
|
|
Для сохранения нормальной жизнедеятельности человека должен в сутки |
|||||||
|
|
потреблять белков не менее 120 усл. ед., жиров – не менее 70 усл. ед. и |
|||||||
|
|
витаминов – |
не менее 10 усл. |
ед. Их содержание в каждой единице |
|||||
6 |
|
продуктов равно: П1 – 0,2; 0,075; 0 усл. ед., П2 – 0,1; 0,1; 0,1 усл. ед. |
|||||||
|
|
Стоимость 1 ед. продукта П1 – 2 руб., П2 – 3 руб. Требуется организовать |
|||||||
|
|
питание человека так, чтобы стоимость продуктов была минимальной, а |
|||||||
|
|
организм получил необходимое количество питательных веществ. |
|||||||
|
|
В районе лесного массива имеются лесопильный завод и фанерная |
|||||||
|
|
фабрика. Чтобы получить 2.5 м3 |
коммерчески реализуемых комплектов |
||||||
|
|
пиломатериалов, необходимо расходовать 2,5 м3 еловых и 7,5 м3 пихтовых |
|||||||
|
|
лесоматериалов. Для приготовления листов фанеры по 100 м2 требуется 5 |
|||||||
|
|
м3 еловых и 10 м3 пихтовых лесоматериалов. Лесной массив содержит 80 |
|||||||
7 |
|
м3 еловых и 180 м3 пихтовых лесоматериалов. Согласно условиям поставок |
|||||||
|
|
в течение планируемого периода необходимо сделать, по крайней мере, 10 |
|||||||
|
|
м3 пиломатериалов и 1200 м3 |
фанеры. Доход с 1 м3 пиломатериалов |
||||||
|
|
составляет 160 руб., а со 100 м3 фанеры - 600 руб. Найти оптимальный план |
|||||||
|
|
производства пиломатериалов и фанеры, при котором прибыль будет |
|||||||
|
|
наибольшей. |
|
|
|
|
|
|
|
|
|
Производство двух видов продукции, А и В, осуществляется путем трех |
|||||||
|
|
операций. Затраты времени на каждую операцию при производстве 1 ед. |
|||||||
|
|
изделия и прибыль от реализации 1 ед. изделия приведены в таблице. |
|||||||
|
|
Сколько изделий каждого вида должно произвести предприятие, чтобы |
|||||||
|
|
получить максимум прибыли, причем число изделий А должно быть не |
|||||||
|
|
менее 10, а изделий В – не более 70 ед.? Максимальный фонд времени на |
|||||||
8 |
|
каждую операцию -600, 700 и 1300 ч соответственно. |
|
|
|||||
|
|
Изделие |
|
Затраты времени на одну операцию, ч |
Прибыль, |
|
|||
|
|
|
|
|
|
|
|
руб. |
|
|
|
|
|
1 |
|
2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А |
|
11 |
|
7 |
16 |
25 |
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
|
6 |
|
8 |
9 |
38 |
|
|
|
|
|
|
|
|
|
|
|
32
|
|
По предписанию врача пациенту необходимо перейти на диету и за сезон |
||||
|
|
употребить питательные вещества, содержащиеся во фруктах и ягодах, в |
||||
|
|
количествах, указанных в таблице. Цена 1 кг фруктов – 30 руб., ягод – 40 |
||||
|
|
руб. |
|
|
|
|
|
|
Вещество |
Содержание вещества в 1 ед. |
Норма |
|
|
|
|
|
продукта, ед. |
потребления |
|
|
|
|
|
|
|
|
|
|
|
|
фрукты |
ягоды |
|
|
|
|
|
|
|
|
|
9 |
|
Р1 |
3 |
1 |
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р2 |
1 |
2 |
20 |
|
|
|
|
|
|
|
|
|
|
Р3 |
2 |
5 |
40 |
|
|
|
|
|
|
|
|
|
|
Р4 |
- |
2 |
14 |
|
|
|
|
|
|
|
|
|
|
Р5 |
2 |
4 |
32 |
|
|
|
|
|
|
|
|
|
|
Определить, какое количество фруктов и ягод необходимо купить за сезон, |
||||
|
|
чтобы выполнить предприятие врача с минимальными затратами. |
||||
|
|
Лесничество имеет 24 га свободной земли под паром и заинтересовано |
||||
|
|
извлечь из нее доход. Оно может выращивать саженцы быстрорастущего |
||||
|
|
гибрида новогодней ели, которые достигают нужных размеров за один год, |
||||
|
|
или бычков, отводя часть земли под пастбище. Деревья продаются |
||||
|
|
партиями по 1000 шт. в каждой. Требуется 1,5 га для выращивания одной |
||||
|
|
партии деревьев и 4 га – вскармливания одного бычка. Лесничество может |
||||
|
|
потратить только 200 ч в год на свое побочное производство. Практика |
||||
10 |
|
показывает, что требуется 20 ч для ухода за одной партией деревьев и 20 ч |
||||
|
|
на уход за одним бычком. Лесничество может израсходовать на эти цели |
||||
|
|
6000 руб. Годовые издержки составляют: на одну партию деревьев 150 |
||||
|
|
руб., на одного бычка 1200 руб. Уже заключен контракт на поставку 2 |
||||
|
|
бычков. Одна новогодняя ель принесет чистый доход в 2.5 руб., один |
||||
|
|
бычок – 5000 руб. Определить оптимальное число новогодних елей и |
||||
|
|
бычков, которое необходимо вырастить, чтобы лесничество получило |
||||
|
|
наибольшую прибыль от их продаж. |
|
|
|
|
33
КОНТРОЛЬНОЕ ЗАДАНИЕ №3
" СТАНДАРТНАЯ ТРАНСПОРТНАЯ ЗАДАЧА”
3.1. ЦЕЛЬ РАБОТЫ
Приобретение навыков построения математических моделей стандартных транспортных задач ЛП и решения их в Microsoft Excel.
3.2.ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1.Согласно номеру своего варианта выберите условие задачи и постройте математическую модель, включая транспортную таблицу.
2. Найдите оптимальное решение задачи в Excel (3.3 варианты).
3. Построить математическую модель и найдите оптимальное решение методом потенциалов (3.4 варианты).
Перед решением задач по данной теме следует изучить следующие теоретические вопросы:
1.Постановка транспортной задачи.
2.Метод наименьшей стоимости.
3.Метод потенциалов.
4.Открытая (не сбалансированная) ТЗ.
Стандартная модель транспортной задачи (ТЗ)
Задача 3.1.
Задача о размещении (транспортная задача).
Пусть необходимо организовать оптимальные по транспортным расходам перевозки муки с двух складов в три хлебопекарни. Ежемесячные запасы муки на складах равны 79,515 и 101,925 т, а ежемесячные потребности хлебопекарен составляют 68,5, 29,5 и 117,4 т соответственно. Мука на складах хранится и транспортируется в мешках по 45 кг. Транспортные расходы (руб./т) по доставке муки представлены в табл.4.2. Между первым складом и второй хлебопекарней заключен договор о гарантированной поставке 4,5 т муки ежемесячно. В связи с ремонтными работами временно невозможна перевозка из второго склада в третью хлебопекарню.
34
Транспортные расходы по доставке муки (руб./т)
Склады |
|
Хлебопекарни |
|
|
Х1 |
Х2 |
Х3 |
||
|
||||
С1 |
350 |
190 |
420 |
|
С2 |
400 |
100 |
530 |
Этапы построения модели
I.Определение переменных.
II.Проверка сбалансированности задачи.
III. Построение сбалансированной транспортной матрицы. IV. Задание ЦФ.
V.Задание ограничений.
Определение переменных
Обозначим через xij [меш.] количество мешков с мукой, которые будут перевезены с i-го склада в j-ю хлебопекарню.
Проверка сбалансированности задачи
Прежде чем проверять сбалансированность задачи, надо исключить объем гарантированной поставки из дальнейшего рассмотрения. Для этого вычтем 4,5 т из следующих величин:
из запаса первого склада a1 79,515 4,5 75,015 т
мес.;
из потребности в муке второй хлебопекарни
b2 29,5 4,500 25,000 т
мес.
Согласно условию задачи мука хранится и перевозится в мешках по 45 кг, то есть единицами измерения переменных xij являются мешки муки.
Но запасы муки на складах и потребности в ней магазинов заданы в тоннах. Поэтому для проверки баланса и дальнейшего решения задачи приведем эти величины к одной единице измерения – мешкам. Например, запас муки на
первом складе |
равен |
75,015 т/мес., или |
75,015 т мес . |
|
1667 меш . мес ., а |
||
0,045 т меш . |
|||||||
|
|
|
|
|
|||
потребность |
первой |
хлебопекарни |
составляет |
68 т/мес., |
или |
||
|
|
35 |
|
|
|
|
|
68,000 т мес . |
1511,1 1512 меш . мес . |
Округление |
при |
расчете |
||
0,045 т меш . |
|
|||||
|
|
|
|
|||
потребностей надо проводить в большую сторону, иначе потребность в муке не будет удовлетворена полностью.
Для данной ТЗ имеет место соотношение
склады |
хлебопекар ни |
|
|
1667 2265 1512 556 2609 .
3932 меш. мес. |
4677 меш. мес. |
Ежемесячный суммарный запас муки на складах меньше суммарной потребности хлебопекарен на 4677-3932=745 мешков муки, откуда следует вывод: ТЗ не сбалансирована.
Построение сбалансированной транспортной матрицы
Сбалансированная транспортная матрица представлена в таблице 3.1. Стоимость перевозки муки должна быть отнесена к единице продукции, то есть к 1 мешку муки. Так, например, тариф перевозки из первого склада в третий магазин равен 420 руб.
т 0,045 т
меш. 18,90 руб.
меш.
Для установления баланса необходим дополнительный фиктивный склад, то есть дополнительная строка в транспортной таблице задачи. Фиктивные тарифы перевозки зададим таким образом, чтобы они были дороже реальных тарифов, например, c3фj 50,00 руб./меш.
Невозможность доставки грузов со второго склада в третью хлебопекарню задается в модели с помощью запрещающего тарифа, который
должен превышать величину фиктивного тарифа, |
например, |
сз |
|
100,00 |
||||
|
|
|
|
|
23 |
|
||
руб./меш. |
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 3.1 |
||||
|
Транспортная матрица задачи |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
Хлебопекарни |
|
|
|
|
Запас, |
|
Склады |
Х1 |
Х2 |
|
Х3 |
|
|
|
мешки |
С1 |
15,75 |
8,55 |
|
18,90 |
|
|
|
1667 |
С2 |
18,00 |
4,50 |
|
100,00 |
|
|
|
2265 |
Сф |
50,00 |
50,00 |
|
50,00 |
|
|
|
745 |
Потребность, мешки |
1512 |
556 |
|
2609 |
|
|
4677 |
|
36
Задание ЦФ
Формальная ЦФ, то есть суммарные затраты на все возможные
перевозки муки, учитываемые в модели, задается следующим выражением: |
||||
L X 15,75x11 |
8,55x12 |
18,90x13 |
|
|
18,00x21 |
4,50x22 |
100,00x23 |
(3.1) |
|
50,00x31 50,00x32 50,00x33 min (руб.
мес.).
При этом следует учитывать, что вследствие использования фиктивных тарифов реальная ЦФ (то есть средства, которые в действительности придется заплатить за транспортировку муки) будет меньше формальной ЦФ (3.1) на стоимость найденных в процессе решения фиктивных перевозок.
Задание ограничений
x |
x |
x |
|
|
|
1667, |
||||
|
11 |
12 |
|
13 |
|
|
|
|
||
x21 x22 x23 2265, |
||||||||||
x |
x |
x |
33 |
745, |
||||||
|
31 |
32 |
|
|
|
|
|
|
||
|
|
x21 x31 |
1512, (меш./мес.) |
|||||||
x11 |
||||||||||
x |
x |
x |
|
|
556, |
|||||
|
12 |
22 |
|
32 |
|
|
|
|
||
x13 x23 x33 2609, |
||||||||||
|
ij |
|
|
|
|
|
|
|
|
|
x |
0 i 1,3; j 1,3 . |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
3.3. ВАРИАНТЫ ЗАДАЧ К КОНТРОЛЬНОМУ ЗАДАНИЮ № 3
Постановка задачи .
На складах хранится мука, которую необходимо завезти в хлебопекарни. Номера складов и номера хлебопекарен выбираются в соответствии с вариантами табл.3.2. Текущие тарифы перевозки муки [руб./т], ежемесячные запасы муки [т/мес.] на складах и потребности хлебопекарен в муке [т/мес.] указаны в табл.3.3.
При этом необходимо учитывать, что из-за ремонтных работ временно нет возможности перевозить муку с некоторых складов в некоторые хлебопекарни. В табл.3.2 это показано в графе "Запрет перевозки" в формате № склада x № хлебопекарни. Например, «2x3» обозначает, что нельзя перевозить муку со склада №2 в хлебопекарню №3.
37
Кроме того, необходимо учесть, что некоторые хлебопекарни имеют договоры на гарантированную поставку муки с определенных складов. В
табл.3.2 это показано в графе "Гарантированная |
поставка" |
в формате |
|
№ склада x № хлебопекарни = объем |
поставки. |
Например, |
«1x4=40» |
обозначает, что между складом №1 и магазином №4 заключен договор на обязательную поставку 40 т муки.
Необходимо организовать поставки наилучшим образом, учитывая, что мука хранится и транспортируется в мешках весом по 50 кг.
Таблица 3.2
Номера складов, хлебопекарен, запрещенные и гарантированные поставки
|
|
|
|
Гарантированная |
№ Варианта |
№ Складов |
№ Хлебопекарен |
Запрет перевозки |
|
|
|
|
|
поставка, т/мес. |
|
|
|
|
|
1 |
1, 2, 3 |
1, 2, 3, 4 |
2x2, 3x4 |
3x3=50 |
|
|
|
|
|
2 |
2, 3, 4, 5 |
1, 2, 5 |
2x2, 3x5 |
3x2=40 |
|
|
|
|
|
3 |
1, 2, 4 |
1, 2, 3, 5 |
1x5, 2x3 |
4x3=45 |
|
|
|
|
|
4 |
1, 2, 3, 4 |
3, 4, 5 |
3x3, 4x5 |
3x5=40 |
|
|
|
|
|
5 |
1, 2, 5 |
2, 3, 4, 5 |
1x4, 5x3 |
1x5=60 |
|
|
|
|
|
6 |
1, 2, 3, 5 |
2, 3, 5 |
5x5, 2x2 |
3x5=30 |
|
|
|
|
|
7 |
2, 3, 4 |
2, 3, 4, 5 |
3x3, 2x5 |
4x3=45 |
|
|
|
|
|
8 |
1, 2, 3, 5 |
1, 2, 4 |
1x2, 5x4 |
3x2=20 |
|
|
|
|
|
9 |
2, 3, 5 |
1, 2, 3, 5 |
5x1, 3x5 |
5x2=30 |
|
|
|
|
|
10 |
2, 3, 4, 5 |
2, 3, 4 |
5x4, 3x2 |
4x3=35 |
|
|
|
|
|
11 |
3, 4, 5 |
1, 2, 3, 4 |
3x4, 5x1 |
4x1=40 |
|
|
|
|
|
12 |
1, 2, 3, 4 |
1, 2, 3 |
3x2, 4x1 |
2x2=50 |
|
|
|
|
|
38
|
|
|
|
|
|
Таблица 3.3 |
|
Запасы, потребности и тарифы перевозок |
|
||||
|
|
|
Хлебопекарни |
|
|
|
Склады |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
Запас, т/мес. |
|
|
|
|
|
|
|
1 |
400 |
600 |
800 |
200 |
200 |
80 |
|
|
|
|
|
|
|
2 |
300 |
100 |
500 |
600 |
500 |
70 |
|
|
|
|
|
|
|
3 |
500 |
200 |
100 |
600 |
300 |
60 |
|
|
|
|
|
|
|
4 |
300 |
700 |
200 |
400 |
900 |
55 |
|
|
|
|
|
|
|
5 |
200 |
500 |
800 |
200 |
400 |
65 |
|
|
|
|
|
|
|
Спрос, т/мес. |
77,86 |
56,78 |
58,88 |
62,44 |
73,92 |
|
|
|
|
|
|
|
|
Задача 3.2.
Задача о назначениях (частный случай транспортной задачи).
Администрация торгового предприятия приняла на работу пять человек. Каждый из них имеет различные способности и навыки и затрачивает различное время на выполнение определенной работы. Необходимо выполнить пять видов работ. Время выполнения работы каждым работником приведено в таблице.
Работник |
|
Время выполнения работы, часы |
|
||
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
М1 |
25 |
16 |
15 |
14 |
13 |
|
|
|
|
|
|
М2 |
25 |
17 |
18 |
23 |
15 |
|
|
|
|
|
|
М3 |
30 |
15 |
20 |
19 |
14 |
|
|
|
|
|
|
М4 |
27 |
20 |
22 |
25 |
12 |
|
|
|
|
|
|
М5 |
29 |
19 |
17 |
32 |
10 |
|
|
|
|
|
|
Требуется назначить на каждый вид работы одного из работников. Как это нужно сделать, чтобы общее время, необходимое для завершения всех видов работ, было минимальным?
39
Определение переменных
xij – факт назначения или не назначения работника Ai на работу B j :
0, если i - й работник не назначен на j - ю работу, xij 1, если i - й работник назначен на j - ю работу.
i 1,5; j 1,5 .
Задание ЦФ
Целевая функция - суммарное время, необходимое для завершения всех видов работ, которое необходимо минимизировать.
L X 25x11 16x12 |
15x13 |
14x14 13x15 25x21 17x22 18x23 23x24 15x25 30x31 |
|
|
15x32 20x33 |
19x34 14x35 |
27x41 20x42 22x43 25x44 12x45 29x51 19x52 17x53 |
= |
|
32x54 10x55 |
min |
|
|
|
Задание ограничений
Функциональные ограничения:
по работам
x11 x12 x13 x14 x15 1, |
|
||||||||||
|
|
x22 |
x 23 |
x24 |
x 25 |
1, |
|
||||
x21 |
|
||||||||||
|
|
x32 |
x33 |
x34 |
x35 |
1, |
(1) |
||||
x31 |
|||||||||||
x |
|
x |
|
x |
|
x |
|
x |
|
1, |
|
|
41 |
|
42 |
|
43 |
|
44 |
|
45 |
|
|
x |
|
x |
52 |
x |
53 |
x |
|
x |
55 |
1. |
|
51 |
|
|
54 |
|
|
|
|||||
по работникам
x11 x21 x31 x41 x51 |
1, |
|
|||||||
x |
x |
x |
32 |
x |
x |
52 |
1, |
|
|
|
12 |
22 |
|
42 |
|
|
|
||
|
|
x23 |
x33 |
x43 |
x53 |
1, |
|
||
x13 |
(2) |
||||||||
x |
x |
x |
|
x |
x |
|
1, |
|
|
|
14 |
24 |
34 |
44 |
54 |
|
|
||
x |
x |
x |
|
x |
x |
|
1. |
|
|
|
15 |
25 |
35 |
45 |
55 |
|
|
||
Прямые ограничения: xij 0 i 1,5; j 1,5 .
Рекомендации к решению задачи о назначениях методом потенциалов.
1. n – количество работников, m – количество работ.
40