Семинар
7. Построение математических моделей
Рассмотрим некоторые наиболее часто используемые в практических целях задачи линейного программирования.
Задача об
оптимальном использовании ресурсов
Предприятие может выпускать n видов
продукции, используя для этого m видов
ресурсов. Известны затраты каждого вида ресурса на производство единицы каждого
вида продукции и прибыль от реализации единицы каждого вида продукции.
Требуется составить план выпуска продукции так, чтобы при данных запасах
ресурсов получить максимальную прибыль.
Составим математическую модель данной задачи.
Введем обозначения:
bi, 
-
запасы i-го
вида ресурса;
aij, ;
- затраты i-го вида ресурса на
производство единицы j-го
вида продукции;
cj, - прибыль от
реализации единицы j-го
вида продукции.
Данные задачи можно
представить в виде таблицы:
|
Виды продукции Виды ресурсов |
1
2 … j …
n |
Запасы ресурсов |
|
|
1 |
a11 a12
… a1j … a1n |
b1 |
|
|
2 |
a21 a22 … a2j … a2n |
b2 |
|
|
… |
… |
… |
|
|
i |
ai1 ai2 … aij … ain |
bi |
|
|
… |
… |
… |
|
|
m |
am1 am2 … amj … amn |
bm |
|
|
Прибыль от реализации единицы продукции |
c1 c2 … cj …
cn |
|
|
Обозначим через xj планируемый выпуск j-го вида продукции; 
- план выпуска
продукции. Тогда прибыль от реализации всей выпускаемой продукции составит
c1x1 + c2x2
+…+cjxj
+…+cnxn.
Составим ограничения по ресурсам. Найдем
расход ресурса первого вида при данном плане выпуска:
a11x1+a12x2+…+a1jхj +…+a1nxn.
Ресурса первого вида имеется
в наличии b1 условных единиц, т.е.
получаем ограничение
a11x1+a12x2+…+a1jхj +…+a1nxn
£ b1.
Аналогично составляем ограничения по всем
остальным видам ресурсов.
Кроме того, xj ³ 0, , так как количество продукции не может быть
отрицательным числом.
Таким образом, математической
моделью данной задачи является задача линейного программирования: найти
наибольшее значение функции
при ограничениях
,
Задача о диете
В продаже имеются различные виды продуктов.
Известны цены продуктов, содержание питательных веществ в единице каждого вида
продукта, медицинские требования на содержание питательных веществ в суточной
диете. Требуется определить, какие продукты и в каком количестве нужно включить
в диету, чтобы она соответствовала всем медицинским требованиям и чтобы
стоимость диеты была минимальной.
Составим математическую
модель данной задачи.
Введем обозначения:
aij
-содержание i-го
питательного вещества в единице j-го
продукта;
bi -
минимальное содержание i-го
питательного вещества в суточной диете;
cj - цена единицы j-го
продукта.
Данные задачи можно
представить в виде таблицы:
|
Виды продуктов Виды питательных веществ |
1 2
… j …
n |
Медицинские требования к диете |
|
1 |
а11 a12
… a1j … a1n |
b1 |
|
2 |
а21 a22
… a2j … a2n |
b2 |
|
… |
… |
… |
|
i |
ai1 ai2 … aij … ain |
bi |
|
… |
… |
… |
|
m |
am1 am2 … amj … amn |
bm |
|
Цена единицы продукта |
с1 c2 …
cj …
cn |
|
Пусть xj единиц j-го продукта включается в
суточную диету, тогда 
- суточная
диета.
Цена диеты:
c1x1 + c2x2
+…+cjxj
+…+cnxn.
Содержание первого питательного вещества в
диете составит
a11x1+a12x2+…+a1jхj +…+a1nxn.
и это количество должно быть не менее чем b1 единиц:
a11x1+a12x2+…+a1jхj +…+a1nxn
£ b1.
Аналогично составляем ограничения по всем
видам питательных веществ.
Кроме того, xj ³ 0, так как количество
продуктов не может быть отрицательным числом.
Математическая модель задачи:
найти минимум функции
при ограничениях:
,
Таким образом, математической
моделью данной задачи является задача линейного программирования.
Задача на
оптимальный раскрой материала
Имеются прутки одинаковой длины, из которых
нужно нарезать определенное количество заготовок заданной длины. Прутки можно
нарезать на заготовки в различных сочетаниях. При каждом варианте нарезания
прутков остаются концевые отрезки.
Требуется определить, какое количество
прутков следует разрезать по каждому варианту, чтобы получить заданное
количество заготовок различной длины и чтобы общая длина концевых отрезков была
минимальной.
Составим математическую
модель данной задачи.
Введем обозначения:
i - номер вида заготовки, ;
j - номер варианта раскроя прутка, ;
aij -
количество заготовок i-го
вида, получаемых из одного прутка, разрезаемого по j-му варианту;
bi -
требуемое число заготовок i-го
вида;
cj - длина концевого отрезка, оставшегося от одного
прутка при разрезании прутка по j-му варианту.
Данные задачи можно
представить в виде таблицы:
|
Варианты раскроя Виды заготовок |
1 2
… j …
n |
План по заготовкам |
|
1 |
а11 a12
… a1j … a1n |
b1 |
|
2 |
а21 a22
… a2j … a2n |
b2 |
|
… |
… |
… |
|
i |
ai1 ai2 … aij … ain |
bi |
|
… |
… |
… |
|
m |
am1 am2 … amj … amn |
bm |
|
Длина концевого отрезка |
с1 c2 …
cj …
cn |
|
Обозначим через хj - число
прутков, разрезаемых по j-му варианту, тогда - план раскроя прутков. Найдем общую длину концевых
отрезков.
По первому варианту планируем
разрезать x1 прутков,
концевой отрезок от одного прутка будет иметь длину с1, тогда общая длина концевых отрезков от х1 прутков составит c1x1. Аналогично общая длина концевых отрезков от х2 прутков, разрезанных по
второму варианту, будет равна c2x2 и т.д.
Следовательно, общая длина
концевых отрезков при разрезании прутков по всем вариантам составляет
.
Составим ограничения по
заготовкам.
Из одного прутка,
разрезаемого по первому варианту, получают
a11 шт.
заготовок первого вида, а из x1 прутков
- a11x1 шт.; по
второму варианту из одного прутка получают a12 шт., а
из x2 прутков
- a12x2 шт. и
т.д., по n-му варианту - a1nxn шт.
Отсюда получаем первое ограничение
a11x1+a12x2+…+a1jхj +…+a1nxn = b1.
Аналогично получаем ограничения по всем
заготовкам.
Кроме того, 
так как число
прутков не может быть отрицательным.
Математическая модель задачи:
найти наименьшее значение функции
при ограничениях:
,
Таким образом, математической
моделью данной задачи является задача линейного программирования.
Задачи
Составить
математические модели следующих задач.
1. Предприятие имеет сырье трех
видов: 1 вида -
|
Сырье |
Нормы расхода сырья на единицу изделия, кг |
|||
|
1 |
2 |
3 |
4 |
|
|
1 |
2 |
2 |
1 |
2 |
|
2 |
4 |
5 |
3 |
6 |
|
3 |
1 |
1 |
2 |
1 |
|
Прибыль от реализации 1 ед. изделия, руб. |
6 |
4 |
7 |
9 |
2.
Предприятие располагает ресурсами сырья, рабочей силой и оборудованием,
необходимыми для производства любого из четырех видов производимых товаров.
Затраты ресурсов на изготовление единицы каждого вида товара и прибыль,
получаемая предприятием, а также объем ресурсов указаны в таблице:
|
Ресурсы |
Затраты ресурсов на 1 ед. товара |
Объем ресурсов |
|||
|
1 |
2 |
3 |
4 |
||
|
Сырье, кг |
3 |
5 |
2 |
4 |
60 |
|
Рабочая сила, чел. |
22 |
14 |
18 |
30 |
400 |
|
Оборудование, станко-ч. |
10 |
14 |
8 |
16 |
130 |
|
Прибыль на 1 ед. товара, руб. |
30 |
25 |
56 |
48 |
|
Составить план выпуска товаров, дающий максимальную
прибыль.
3. Для изготовления трех видов изделий (А, В,
и С) фабрика расходует в качестве
сырья сталь и цветные металлы, имеющиеся в ограниченном количестве. На
изготовлении указанных изделий заняты токарные и фрезерные станки.
В таблице приведены объем
ресурсов, которыми располагает предприятие, и нормы расхода перечисленных
ресурсов на единицу изделия. Кроме того, в последней строке таблицы указана
прибыль предприятия от продажи единицы каждого изделия. Определить план выпуска
продукции, при котором будет получена максимальная прибыль.
|
Ресурсы |
Нормы расхода ресурсов на единицу изделия |
Объем ресурсов |
||
|
А |
В |
С |
||
|
10 |
70 |
10 |
57000 |
|
|
Цветные металлы, кг |
20 |
50 |
10 |
49000 |
|
Токарные станки, станко-ч |
300 |
400 |
100 |
560000 |
|
Фрезерные станки, станко-ч |
200 |
100 |
100 |
340000 |
|
Прибыль, тыс. руб. |
3 |
8 |
2 |
|
4. Предприятие
располагает ресурсами сырья, рабочей силой и оборудованием, необходимыми для
производства любого из четырех видов производимых товаров. Затраты ресурсов на
изготовление единицы каждого вида товара, прибыль, получаемая предприятием, а
также объем ресурсов указаны в таблице. Определить оптимальный ассортимент при
условии, что товаров 1 вида выпустят не более 10 ед., 2 вида не менее 8 ед., а
3 и 4 видов не менее 10 ед.
|
Ресурсы |
Затраты ресурсов на единицу товара |
Объем ресурсов |
|||
|
1 |
2 |
3 |
4 |
||
|
Сырье, кг |
3 |
5 |
1 |
4 |
600 |
|
Рабочая сила, чел. |
21 |
10 |
12 |
30 |
4000 |
|
Оборудование, станко-ч |
10 |
14 |
8 |
16 |
16000 |
|
Прибыль на единицу товара, руб. |
30 |
25 |
50 |
50 |
|
5. Для
нарезки заготовок длиной 20, 25 и 30 см используются прутки длиной 75 см.
Требуется за смену нарезать следующее количество заготовок: длиной 20 см - 300
шт., длиной 25 см - 270 шт., длиной 30 см - 350 шт. Из одного прутка можно
нарезать заготовки различной длины. Количество заготовок, которые можно
нарезать из одного прутка по различным вариантам разрезки, приведено в таблице.
При каждом варианте разрезки будут оставаться концевые остатки, величины
которых также приведены в таблице:
|
Заготовка |
Длина заготовки, см |
Количество заготовок из 1 прутка |
||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
|
1 |
20 |
3 |
1 |
1 |
0 |
2 |
0 |
2 |
|
2 |
25 |
0 |
2 |
1 |
0 |
0 |
3 |
1 |
|
3 |
30 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
|
Концевой
остаток, см |
15 |
5 |
0 |
15 |
5 |
0 |
10 |
|
Определить, какое число прутков необходимо нарезать
по различным вариантам, чтобы число заготовок соответствовало заданной
программе, и чтобы при этом общая длина всех концевых остатков была
минимальной.
6. Предприятие
производит пиломатериалы и фанеру,
используя для этого еловые и пихтовые лесоматериалы. Для приготовления
Составить задачу нахождения оптимального плана производства предприятия,
если по условиям поставок необходимо произвести не менее 10 м3
пиломатериалов и 1200 м2 фанеры. Доход с 1 м3
пиломатериалов составляет 16 ед., а со 100 м2 фанеры 60 ед.
7. Фирма выпускает радиоприемники трех различных
моделей: А, В, С. Каждое изделие
указанных моделей приносит доход в размере 8, 15, 25 ед., соответственно.
Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 модели В и 75 модели С. Каждая
модель характеризуется определенным временем, необходимым для изготовления
соответствующих деталей, сборки изделия и его упаковки. Так, в частности, в
расчете на 10 приемников модели А
требуется 3 ч для изготовления деталей, 4 ч на сборку и 1 ч на упаковку.
Соответствующие показатели в расчете на 10 приемников модели В равны 3,5 , 5 и 1,5, а на 10
приемников модели С - 5, 8 и 3. В
течение недели фирма может израсходовать на производство деталей 150 ч, на
сборку 200 ч и на упаковку 60 ч.
Составить задачу нахождения оптимального производственного плана.
Привести ее к каноническому виду.
8. Нефтеперерабатывающее
предприятие использует два технологических процесса приготовления смесей.
Технологический процесс 1 характеризуется следующими показателями: из 1 ед.
объема сырой нефти А и 3 ед. объема
сырой нефти В получают 5 ед. объема
бензина Х и 2 ед. объема бензина Y. Технологический процесс 2:
из 4 ед. объема сырой нефти А и 2 ед.
объема сырой нефти В получают 3 ед.
объема бензина Х и 8 ед. объема
бензина Y. Запасы сырой нефти
составляют 100 ед. объема нефти А и
150 ед. объема нефти В. По условию
поставки, требуется произвести не менее 200 ед. объема бензина Х и 75 ед. бензина Y. Доходы с 1 ед. объема
продукции, полученной с помощью технологических процессов 1 и 2, составляют 15
и 20 ед., соответственно.
9. При составлении суточного
рациона кормления скота можно использовать сено свежее (не более 50 кг) и силос
(не более 85 кг). Рацион должен обладать определенной питательностью (число
кормовых единиц не менее 30) и содержать питательные вещества: белок (не менее
1 кг), кальций (не менее 100 г) и фосфор (не менее 80 г).
В следующей таблице приведены данные о
содержании указанных компонентов в
|
Количество кормовых единиц |
Белок, г/кг |
Кальций, г/кг |
Фосфор, г/кг |
Сто-имость, ед./кг |
|
|
Сено свежее |
0,5 |
40 |
1,25 |
2 |
1,2 |
|
Силос |
0,5 |
10 |
2,5 |
1 |
0,8 |
10. Листы материала размером 6х13 надо раскроить так,
чтобы получились заготовки двух типов: 800 шт. заготовок размером 4х5 и 400 шт.
заготовок размером 2х3. Способы раскроя материала и количество получаемых при этом заготовок различных типов указаны
в таблице. Составить план раскроя с минимальным расходом материала.
|
Размер заготовки, м |
Способы раскроя |
|||
|
1 |
2 |
3 |
4 |
|
|
4х5 |
3 |
2 |
1 |
0 |
|
2х3 |
1 |
6 |
9 |
13 |