Примеры задач линейного программирования

1. Нефтяная компания "РТ" для улучшения эксплуатационных качеств и снижения точки замораживания дизельного топлива, которое она производит, добавляет в него определенные химикаты. В каждом бензобаке объемом 1000 л должно содержаться не менее 40 мг химической добавки X, не менее 14 мг химической добавки Y и не менее 18 мг химической добавки Z. Необходимые химические добавки в форме готовых смесей поставляют "РТ" две химические компании А и В. В нижеследующей таблице приведено содержание химических добавок в каждом продукте, поставляемом указанными компаниями.

Продукт

Химические добавки, мг/л

X

Y

Z

A

4

2

3

B

5

1

1

Стоимость продукта А - 1,50 ф. ст. за 1 л, а продукта В - 3,00 ф. ст. за 1 л. Требуется: найти ассортиментный набор продуктов А и В, минимизирующий общую стоимость добавленных в топливо химикатов.
Рекомендации к решению: после составления экономико-математической модели задачи, ее можно будет решить симплекс-методом.

2. "Princetown Paints Ltd" выпускает три основных типа румян - жидкие, перламутровые и матовые - с использованием одинаковых смесеобразующих машин и видов работ. Главному бухгалтеру фирмы было поручено разработать для компании план производства на неделю. Информация о ценах продаж и стоимости 100 л товара приведена в таблице (ф. ст.).



Румяна

Жидкие

Перламутровые

Матовые

Цена продажи на 100 л

120

126

110

Издержки производства на 100 л:


Стоимость сырья

11

25

20

Стоимость трудозатрат

30

36

24

Стоимость приготовления смеси

32

20

36

Другие издержки

12

15

10

Стоимость 1 чел.-ч составляет 3 ф. ст. а стоимость 1 ч приготовления смеси -4 ф. ст. Фонд рабочего времени ограничен 8000 чел.-ч. в неделю, а ограничение на фонд работы смесеобразующих машин равно 5900 ч. в неделю.
В соответствии с контрактными соглашениями компания должна производить 25000 л матовых румян в неделю. Максимальный спрос на жидкие румяна равен 35000 л в неделю, а на перламутровые румяна - 29000 л в неделю.
Требуется: определить оптимальные объемы производства в неделю, при которых достигается максимальное значение получаемой за неделю прибыли, и соответствующее значение прибыли.
Методические рекомендации к решению: необходимо составить экономико-математическую модель задачи, после чего решить симплекс-методом в Excel.

3. Компания "Bermuda Paint" - частная промышленная фирма, специализирующаяся на производстве технических лаков. Представленная ниже таблица содержит информацию о ценах продажи и соответствующих издержках производства единицы полировочного и матового лаков.


Лак

Цена продажи 1 галлона,
ф. ст.

Издержки производства
1 галлона, ф. ст.

Матовый

13,0

9,0

Полировочный

16,0

10,0

Для производства 1 галлона матового лака необходимо затратить 6 мин трудозатрат, а для производства одного галлона полировочного лака - 12 мин. Резерв фонда рабочего времени составляет 400 чел.-ч. в день. Размер ежедневного запаса необходимой химической смеси равен 100 унциям, тогда как ее расход на один галлон матового и полировочного лаков составляет 0,05 и 0,02 унции соответственно. Технологические возможности завода позволяют выпускать не более 3000 галлонов лака в день.
В соответствии с соглашением с основным оптовым покупателем компания должна поставлять ему 5000 галлонов матового лака и 2500 галлонов полировочного лака за каждую рабочую неделю (состоящую из 5 дней). Кроме того, существует профсоюзное соглашение, в котором оговаривается минимальный объем производства в день, равный 2000 галлонов. Администрации данной компании необходимо определить ежедневные объемы производства каждого вида лаков, которые позволяют получать максимальный общий доход.
Требуется: определить ежедневный оптимальный план производства и соответствующую ему величину дохода.
Методические рекомендации к решению: необходимо составить экономико-математическую модель задачи, после чего решить симплекс-методом в Excel.

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


Завод

Транспортные издержки, ф. ст. за единицу
Торговый склад

Предложение
т

1

2

3

4

5

A

20

27

33

25

34

200

B

22

36

34

28

26

250

C

26

29

27

26

28

300

Потребность, т

100

150

200

100

200


Требуется определить минимальную стоимость транспортировки на декабрь.
Методические рекомендации к решению: проверить решение можно с помощью сервиса транспортная задача.

5. Администрация деревоперерабатывающего предприятия "Vibra" приняла на работу пять человек. Каждый из них имеет различные способности и навыки и затрачивает различное время на выполнение определенной работы. В настоящее время необходимо выполнить пять видов работ. Время выполнения работы каждым работником приведено в таблице:


Работник

Время выполнения, ч

Работы 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

Требуется назначить на каждый вид работы одного из работников. Как это нужно сделать, чтобы общее время, необходимое для завершения всех видов работ, было минимальным?
Методические рекомендации к решению: данный тип задач относится к задачам о назначении.

6. Механический завод при изготовлении двух типов деталей использует токарное, фрезерное и сварочное оборудование. При этом обработку каждой детали можно вести двумя различными технологическими способами. Полезный фонд времени работы каждой группы оборудования (в станко-часах), нормы расхода времени при обработке детали на соответствующем оборудовании по данному технологическому способу и прибыль от выпуска единицы деталей каждого вида даны в таблице.


Оборудование

Детали

Полезный фонд времени, станко-ч.

1

2

Технологические способы

1

2

1

2

Фрезерное

2

2

3

0

20

Токарное

3

1

1

2

37

Сварочное

0

1

1

4

30

Прибыль, усл. ед.

11

6

9

6

 

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

Решение.
Обозначим через xij объем выпуска i-й детали j-м технологическим способом.
Блок ограничений на ресурсы представлен ограничениями на количество рабочего времени каждого станка:
фрезерный: (2x11 + 2x12) + (3x21) ≤ 20,
токарный: (3x11 + x13) + (x21 + 2x22) ≤ 37,
сварочный: (x12) + (x22 + 4x23) ≤ 30.
Построим целевую функцию. Задача состоит в максимизации прибыли компании. Поэтому в качестве целевой функции получим следующее выражение:
       11x11 + 6x12 + 9x21 + 6x22 → max

загрузка...