2. Практические занятия
Модуль 1
Задание 1. Формализация задач линейного программирования
Пример 1.1. Фабрика выпускает продукцию двух видов: П1 и П2. Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта - A, B, C. Максимально возможные суточные запасы этих продуктов составляют 6, 8 и 5 т соответственно. Расходы сырья A, B, C на 1 тыс. изделий П1 и П2 приведены в табл. 1.1.
Изучение рынка сбыта показало, что суточный спрос на изделия П2 никогда не превышает спроса изделия П1 более чем на 1 тыс. шт.
Кроме того, установлено, что спрос на изделия П2 никогда не превышает 2 тыс. шт. в сутки.
Оптовые цены за 1 тыс. шт. изделий равны, соответственно, П1 - 3 тыс. руб., П2 - 2 тыс. руб.
Таблица 1.1
-
Исходный
продукт
|
Расход исходных продуктов на производство
1 тыс. изделий (т.)
|
Максимально возможный запас (т.)
|
П1
|
П2
|
A
|
1
|
2
|
6
|
B
|
2
|
1
|
8
|
C
|
1
|
0.8
|
5
|
Необходимо спланировать производство так, чтобы доход от реализации продукции фабрики был максимальным?
Построение математической модели следует начать с идентификации переменных (искомых величин), но так, чтобы после этого целевая функция и ограничения могли быть выражены через соответствующие переменные.
В рассматриваемом примере имеем следующее:
Переменные. Так как нужно максимизировать прибыль, а она зависит от объемов производства каждого вида продукции, то переменными являются:
 - суточный объем производства изделия П1 в тыс. шт.;
 - суточный объем производства изделия П2 в тыс. шт.
Целевая функция. Так как стоимость 1 тыс. изделий П1 равна 3 тыс. руб., суточный доход от ее продажи составит 3 тыс. руб. Аналогично доход от реализации тыс. шт. П2 составит 2 тыс. руб. в сутки. При допущении независимости объемов сбыта каждого из изделий общий доход равен сумме двух слагаемых - дохода от продажи изделий П1 и дохода от продажи изделий П2.
Обозначив доход (в тыс. руб.) через  , можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения и , максимизирующие величину общего дохода:
 , 
Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход исходных продуктов A, B и С и спрос на изготовляемую продукцию, что можно записать так:
-
Суточный расход исходного продукта для производства обоих видов изделия
|
|
Максимально возможный суточный запас данного исходного продукта
|
Это приводит к трем ограничениям:
+ 2  6 (для А),
2 + 8 (для В),
+ 0.8 5 (для С).
Ограничения на величину спроса на продукцию имеют вид:
- 1 (соотношение величин спроса на изделия П1 и П2),
2 (максимальная величина спроса на изделия П2).
Вводятся также условия неотрицательности переменных, т. е. ограничения на их знак:
  0 (объем производства П1),
0 (объем производства П2).
Эти ограничения заключаются в том, что объемы производства продукции не могут принимать отрицательных значений.
Следовательно, математическая модель записывается следующим образом.
Определить суточные объемы производства ( и ) изделий П1 и П2 в тыс. шт., при которых достигается
при наличии ограничений
Математическая модель задачи получена. Отметим, что на 3 этапе исследования операций следует выбрать метод решения задачи, для чего её нужно отнести к некоторому классу задач. Полученная модель относится к задачам линейного программирования, так как целевая функция и функции ограничений – линейные, а на переменные наложено ограничение неотрицательности. Следовательно, решить задачу, провести анализ полученного решения можно с помощью методов решения задач линейного программирования, которые будут рассмотрены ниже.
Составить математические модели следующих задач.
Вариант № 1. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей: Х и Y. Завод располагает фондом рабочего времени в 4000 чел. - ч. в неделю. Для производства одной детали типа Х требуется 1 чел. - ч, а для производства одной детали типа Y — 2 чел. - ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа Х и 1750 деталей типа Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.
Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ф. ст., а от производства одной детали типа Y—40 ф. ст.?
Вариант № 2. Завод по производству электронного оборудования выпускает персональные компьютеры и системы подготовки текстов. В настоящее время освоены четыре модели:
а) "Юпитер" — объем памяти 512 Кбайт, одинарный дисковод;
б) "Венера" — объем памяти 512 Кбайт, двойной дисковод;
в) "Марс" — объем памяти 640 Кбайт, двойной дисковод;
г) "Сатурн" — объем памяти 640 Кбайт, жесткий диск.
В производственный процесс вовлечены три цеха завода — цех узловой сборки, сборочный и испытательный. Распределение времени, требуемого для обработки каждой модели в каждом цехе, а также максимальные производственные мощности цехов приведены в табл. Отдел исследований рынка производит периодическую оценку потребительского спроса на каждую модель. Максимальные прогнозные значения спроса и доходы от реализации единицы продукции каждой модели также содержатся в таблице.
Построить модель задачи для изложенной проблемы производства изделий в ассортименте, если цель состоит в максимизации общего ежемесячного дохода.
Время, требуемое на обработку каждой модели в каждом цехе
Цех
|
Время на единицу продукции, ч
|
Максимальная
производственная мощность
|
"Юпитер"
|
"Венера"
|
"Марс"
|
"Сатурн"
|
|
Узловой сборки
|
5
|
8
|
20
|
25
|
800
|
Сборочный
|
2
|
3
|
8
|
14
|
420
|
Испытательный
|
0,1
|
0.2
|
2
|
4
|
150
|
Максимальное прогнозное значение спроса за месяц
|
100
|
45
|
25
|
20
|
|
Доход, ф.ст.
|
15
|
30
|
120
|
130
|
|
Вариант № 3. Менеджер по ценным бумагам намерен разместить 100000 ф. ст. капитала таким образом, чтобы получать максимальные годовые проценты с дохода. Его выбор ограничен четырьмя возможными объектами инвестиций: А, В, С и D. Объект А позволяет получать 6% годовых, объект В — 8% годовых, объект С— 10%, а объект D — 9% годовых. Для всех четырех объектов степень риска и условия размещения капитала различны. Чтобы не подвергать риску имеющийся капитал, менеджер принял решение, что не менее половины инвестиций необходимо вложить в объекты А и В. Чтобы обеспечить ликвидность, не менее 25% общей суммы капитала нужно поместить в объект D. Учитывая возможные изменения в политике правительства, предусматривается, что в объект С следует вкладывать не более 20% инвестиций, тогда как особенности налоговой политики требуют, чтобы в объект А было вложено не менее 30% капитала.
Вариант № 4. Компания "Princetown Paints Ltd" выпускает три основных типа румян — жидкие, перламутро вые и матовые — с использованием одинаковых смесеобразующих машин и видов работ. Для обеспечения максимального значения получаемой за неделю прибыли главному бухгалтеру фирмы было поручено разработать для компании план производства на неделю. Информация о ценах продаж и стоимости 100 л товара приведена в таблице (ф. ст.). Стоимость 1 чел.-ч составляет 3 ф. ст. а стоимость 1 ч приготовления смеси — 4 ф. ст. Фонд рабочего времени ограничен 8000 чел.-ч. в неделю, а ограничение на фонд работы смесеобразующих машин равно 5900 ч в неделю.
В соответствии с контрактными соглашениями компания должна производить 25000 л матовых румян в неделю. Максимальный спрос на жидкие румяна равен 35000 л в неделю, а на перламутровые румяна — 29000 л в неделю.
Исходные данные
|
Румяна
|
Жидкие
|
Перламутровые
|
Матовые
|
Цена продажи на 100 л
|
120
|
126
|
110
|
Издержки производства товаров на 100 л:
|
- стоимость сырья
|
11
|
25
|
20
|
- стоимость трудозатрат
|
30
|
36
|
24
|
- стоимость приготовления смеси
|
32
|
20
|
36
|
- другие издержки
|
12
|
15
|
10
|
Вариант № 5. Администрация компании "Nemesis Company", осуществляя рационализаторскую программу корпорации, приняла решение о слиянии двух своих заводов в Аббатсфилде и Берчвуде. Предусматривается закрытие завода в Аббатсфилде и за счет этого — расширение производственных мощностей предприятия в Берчвуде. На настоящий момент распределение рабочих высокой и низкой квалификации, занятых на обоих заводах, является следующим:
Квалификация рабочих
|
Аббатсфилд
|
Берчвуд
|
Высокая
Низкая
|
200
300
|
100
200
|
Итого
|
500
|
300
|
В то же время после слияния завод в Берчвуде должен насчитывать 240 рабочих высокой и 320 рабочих низкой квалификации.
После проведения всесторонних переговоров с привлечением руководителей профсоюзов были выработаны следующие финансовые соглашения:
1. Все рабочие, которые попали под сокращение штатов, получат выходные пособия следующих размеров:
- квалифицированные рабочие: 2000 ф. ст.;
- неквалифицированные рабочие: 1500 ф. ст.
2. Рабочие завода в Аббатсфилде, которые должны будут переехать, получат пособие по переезду в размере 2000 ф. ст.
3. Во избежание каких-либо преимуществ для рабочих Берчвудского завода доля бывших рабочих завода в Аббатсфилде на новом предприятии должна совпадать с долей бывших рабочих Берчвудского завода.
Построить модель задачи, в которой определяется, как осуществить выбор работников нового предприятия из числа рабочих двух бывших заводов таким образом, чтобы минимизировать общие издержки, связанные с увольнением и переменой места жительства части рабочих. |
