Задача о раскрое материалов.

На раскрой (распил, обработку) поступает материал одного образца в количестве A единиц. Требуется изготовить из него m разных комплектующих изделий в количествах, пропорциональных числам b_i (i = 1,…, m) – условие комплектности.

Каждая единица материала может быть раскроена n различными способами, причем использование j-го способа (j = 1,…, n) дает a_ij единиц i-го изделия (i = 1,…, m).

Необходимо найти план раскроя, обеспечивающее максимальное количество комплектов.

Обозначим x_j – число единиц материала, раскраиваемых j-ым способом,

x – число изготавливаемых комплектов изделий.

Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то x_j = A.

Требование комплектности выразится уравнениями

x_jּa_ij = b_iּx (i = 1,…, m)

Кроме того x_j ≥ 0 (j = 1,…, n).

Практический блок

Пример

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

1. По данным, приведенным в таблице 2.2.3 составить систему математических зависимостей (неравенств) и целевую функцию.

2. Изобразить геометрическую интерпретацию задачи и найти оптимальное решение.

3. Провести аналитическую проверку и определить значение целевой функции.

4. Определить избытки ресурсов.

5. Вычислить объективно обусловленные оценки.

6. Исследовать устойчивость решения.

Таблица 2.2.3 – Матрица удельных нормативов.

Продукция	Сырье	Прибыль на одно изделие
Рес. 1	Рес. 2	Рес. 3
I. Изделие 1	2.4	8.0	6.2	50 ()
II. Изделие 2	12.2	5.4	2.2	40 ()
Наличие ресурсов				–

Решение:

1. Обозначим:

– объем изделия 1;

– объем изделия 2.

Опишем модель с помощью системы неравенств линейных уравнений:

;

;

;

;

– целевая функция (критерий оптимальности).

Графическое решение системы и определение оптимальных объемов производства.

0АВСD – это допустимое решение системы неравенств, в пределах существующих ресурсов. Используя нормаль целевой функции, определим максимально-удаленную точку от начала координат. Это и будет решением системы неравенств. Как видно из рисунка 2.2.3, такая точка будет т.В.

Рисунок 2.2.3. Графическое решение системы линейных уравнений

Где:

I – первый ресурс;

In – нормаль первого ресурса из начала координат;

II – второй ресурс;

IIn – нормаль второго ресурса из начала координат;

III – третий ресурс;

IIIn – нормаль третьего ресурса из начала координат;

F – нормаль целевой функции.

Координаты т.В ( и ) будут пересечение прямых I и II.

3. Найдем решение системы неравенств:

И рассчитаем максимальную прибыль:

4. Определим избытки ресурсов (скрытые резервы):

Объективно обусловленные оценки ресурсов

Объективно обусловленные оценки ресурсов (далее О.О.О.) показывают, на сколько изменится прибыль, если ресурс увеличить на единицу или сколько прибыли добавляет каждая единица ресурса.

О.О.О. 1-го ресурса.

Увеличим на единицу ограничение первого ресурса и определим оптимальный объем производства.

Найдем решение системы неравенств:

Тогда максимальная прибыль при таких объемах производства будет:

Рассчитаем О.О.О. первого ресурса:

О.О.О. 2-го ресурса.

Увеличим на единицу ограничение второго ресурса и определим оптимальный объем производства.

Найдем решение системы неравенств:

Тогда максимальная прибыль при таких объемах производства будет:

Рассчитаем О.О.О. второго ресурса:

О.О.О. 3-го ресурса.

О.О.О несущественного ресурса равна нулю, т.к. ресурс и так в избытке, т.е.:

Устойчивость решения при изменении удельной прибыли.

В реальных условиях удельная прибыль от производства продукции и может меняться. Поэтому составим соотношение устойчивости, т.е. найдем пределы, до которых может отклоняться нормаль целевой функции, чтобы решение системы оставалось в точке В.. Руководствуясь правилом, что у больших углов больший тангенс, составим соотношение устойчивости:

; ; .

Тесты

1. Какая задача является задачей линейного программирования:

а) управления запасами;

б) составление диеты;

в) формирование календарного плана реализации проекта.

2. Тривиальными ограничениями задачи линейного программирования называются условия:

а) ограниченности и монотонности целевой функции;

б) не отрицательности всех переменных;

в) не пустоты допустимого множества.

3. Если в задаче линейного программирования допустимое множество не пусто и целевая функция ограничена, то:

а) допустимое множество не ограничено;

б) оптимальное решение не существует;

в) существует хотя бы одно оптимальное решение.

4. Линейное программирование – это раздел исследования операций, изучающий:

а) методы нахождения экстремума линейной функции;

б) методы нахождения экстремума линейной функции с линейными ограничениями;

в) методы нахождения экстремума произвольной функции с линейными ограничениями.

5. Область допустимых решений задачи линейного программирования определяется:

а) системой линейных неравенств и условиями неотрицательности переменных;

б) системой уравнений общего вида и условиями неотрицательности переменных;

в) системой линейных уравнений и условиями неотрицательности переменных.

6. Симплекс-метод решения задачи ЛП – это:

а) метод целенаправленного перебора допустимых базисных решений в направлении оптимального значения целевой функции;

б) метод последовательного перебора допустимых базисных решений задачи ЛП;

в) метод нахождения допустимых базисных решений задачи ЛП.

7. Где довольно часто встречаются на практике задачи линейного программирования?

а) при решении проблем, связанных с распределением ресурсов;

б) при планировании производства;

в) при организации работы транспорта;

г) содержание п. а, б, в.

д) содержание п. а, б.

8. Объективно-обусловленные оценки ресурсов показывают:

а) избытки несущественных ресурсов;

б) на сколько увеличится прибыль, если ресурс увеличить на единицу;

в) оптовую цену.

9. Соотношение устойчивости показывает:

а) при каких диапазонах изменения коэффициентов целевой функции оптимальное решение сохранится;

б) отношение коэффициентов целевой функции к оптимальным объемам производства;

в) отношение коэффициентов целевой функции к нормативной потребности в ресурсах.

10. Какая задача не описывается моделью линейного программирования:

а) управление запасами на складе;

б) Задача использования ресурсов;

в) Задача оптимального использования удобрений;

г) Задача составления диеты;

д) Задача о раскрое материалов.

Ответы к тестам

Контрольные вопросы

1. В задаче составления плана производства дать постановку экономической задачи.

2. Для задачи составления плана производства описать переменные и параметры задачи.

3. Для задачи составления плана производства описать основные экономические условия.

4. Для задачи составления плана производства сформулировать ограничения задачи.

5. Что принимается в качестве целевой функции в задаче составления плана производства?

6. Дать экономический смысл точного равенства в ограничении задачи составления плана производства.

7. Экономический смысл оптимального решения в задаче составления плана производства.

8. Экономический смысл строгого неравенства в ограничении задачи составления плана производства.

9. Для задачи составления плана производства записать двойственную задачу.

10. В двойственной задаче для задачи составления плана производства привести экономический смысл целевой функции.

11. В двойственной задаче для задачи составления плана производства привести экономический смысл ограничений.

12. В двойственной задаче для задачи составления плана производства привести экономический смысл переменных.

13. Проанализировать изменение целевой функции в линейной модели производства при изменении цен реализации продукции.

14. Проанализировать изменение целевой функции в линейной модели производства при изменении запаса дефицитного ресурса.

15. Проанализировать изменение целевой функции в линейной модели производства при изменении запаса недефицитного ресурса.

16. Привести экономический смысл связи целевых функций прямой и двойственной задач в линейной модели производства.

17. Указать отличие линейных экономических моделей от нелинейных.

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

19. Как поставить задачу линейного программирования?

20. Каковы особенности графического метода решения задачи линейного программирования: построение области допустимых значений, нахождение оптимальной точки или прямой.

21. Указать особенности двойственной задачи линейного программирования.

Задания и задачи

Задача 1. а) Построить математическую модель следующей экономической задачи, решить ее графическим методом.

б) Составить задачу двойственную к данной.

При откорме каждое животное ежедневно получает не менее 9 единиц питательного вещества А, не менее 8 единиц вещества В, не менее 12 единиц вещества С. Содержание количества единиц питательных веществ в 1 кг корма, приведены в таблице 2.2.4. Известно, что для составления рациона используются 2 вида корма. Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.

Таблица 2.2.4

Задача 2. Решите следующую задачу ЛП:

F(x) = 3 x ₁ + 4 x ₂→ max при ограничениях

x ₁ + 2 x ₂ ≤ 4

x ₁ + x ₂ ≤ 3

2 x ₁ + x ₂ ≤ 3

x ₁, x ₂ ≥ 0

Задача 3. а) Построить математическую модель следующей экономической задачи, решить ее графическим методом.

б) Составить задачу двойственную к данной.

Для изготовления двух видов продукции используется 3 вида сырья: А, В и С. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единиц продукции, приведены в таблице 2.2.5. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Таблица 2.2.5

Задача 4. Решите следующую задачу ЛП:

F(x) = x ₁ – x ₂ → max при ограничениях

–2 x ₁ + x ₂ ≤ 2

x ₁ – 2 x ₂ ≤ 2

x ₁ + x ₂ ≤ 5

x ₁, x ₂ ≥ 0.

Задача 5. Фирма производит два вида продукции, используя для этого два вида ресурсов. Цены реализации – 120 д.е. и 90 д.е. Технологическая матрица задана в виде таблицы

Запас ресурсов – 3000 ед. ресурса № 1, 3600 ед. ресурса № 2. Требуется определить план производства, максимизирующий доход.

Записать математическую модель.

Найти наилучший план производства.

Найти максимальный доход.

Определить оценки стоимости ресурсов.

Задача 6. Составить экономико-математическую модель: Торговое предприятие реализует 4 группы товаров (А, В, С и D). Нормы затрат ресурсов на каждый тип товаров, лимиты ресурсов, а также доход на единицу каждой продукции заданы в таблице 2.2.6. Определить плановый объем продаж так, чтобы доход торгового предприятия был максимален.

Таблица 2.2.6

Задача 7. Магазин продает два вида безалкогольных напитков: Кока–Колу и квас. Доход от одной банки колы составляет 5 центов, а от кваса – 7 центов. В среднем магазин продает не более 500 банок обоих напитков ежедневно. Отделом продаж определено, что объемы продаж колы и кваса в натуральном исчислении должны соотноситься не менее чем 1:2. Кроме того, известно, что магазин продает не менее 100 банок колы в день.

Как наилучшим образом спланировать руководству магазина запасы напитков в начале дня?

Задача 8. Мебельная фабрика для сборки столов и стульев привлекает к работе на 10 дней четырех столяров. Каждый столяр затрачивает 2 часа на сборку стола и 30 минут – на сборку стула. Покупатели обычно приобретают вместе со столом от четырех до шести стульев. Доход от одного стола составляет $135 и $50 – от одного стула. На фабрике установлен 8-часовой рабочий день.

Руководство фабрики хотело бы оптимизировать свое производство.

Задача 9. Банк в течение нескольких месяцев планирует вложить до $200 000 в кредитование частных лиц и покупок автомобилей. Банковские комиссионные составляют 14% при кредитовании частных лиц и 12% при кредитовании покупок автомобилей. Оба типа кредитов возвращаются в конце годичного периода кредитования. Известно, что 3% клиентских и 2% автомобильных кредитов никогда не возвращаются. Объемы кредитов на покупку автомобилей обычно более чем в 2 раза превышают объемы кредитов для частных лиц.

Руководство банка хотело бы знать, как можно оптимизировать размещение средств по указанным типам кредитов.

Задача 10. Завод производит 2 типа микросхем, каждый на отдельно линии. Производительность этих линий составляет 600 и 750 микросхем в день. Для производства микросхем первого типа необходимо 10 единиц некоторого комплектующего, а второго типа – 8 единиц этого же комплектующего. Поставщик может обеспечить на день 8 000 единиц этого комплектующего. Доход от микросхем первого типа составляет $60, а второго – $40. Каким образом можно оптимально спланировать производство?

Задача 11. Мебельная фабрика собирает из готовых комплектующих 2 вида кухонных шкафов: обычные и люкс. Обычный шкаф покрывается белой краской, а люкс – лаком. Покраска и покрытие лаком производятся на одном производственном покрасочном участке. Сборочная линия фабрики ежедневно может собирать не более 200 обычных шкафов и 150 шкафов типа люкс. Лакирование шкафа типа люкс требует вдвое больше времени, чем покраска одного простого шкафа. Если покрасочный участок занят только лакированием, то за день здесь можно подготовить 180 шкафов типа люкс. Фабрика оценивает доход от обычных шкафов и шкафов люкс в $100 и $140 соответственно. Составьте оптимальное ежедневное расписание работы покрасочного участка.

Задача 12. Фирма Wild West выпускает ковбойские шляпы двух типов (А и В). Производство шляпы первого типа требует в 2 раза больше временных ресурсов, чем производство шляпы второго типа. Если бы фирма выпускала только шляпы типа В, суточный объем производства мог бы составить 400 таких шляп. Рынок накладывает ограничения: суточный объем сбыта шляп типа А не более 150, а шляп типа В – 200 штук. Доход от производства шляп типа А составляет $8, а шляп типа В – $5. Определить, как наилучшим образом спланировать производство шляп.

Задача 13. Компания производит два вида продукции: А и В. Объем продаж продукта А составляет не менее 80% от общего объема продаж продуктов А и В. Вместе с тем компания не может производить более 100 единиц продукта А в день. Для производства этих продуктов используется одно и то же сырье, поступление которого ограничено 240 кг. в день. На изготовление единицы продукта А расходуется 2 кг. сырья, а продукта В – 4 кг. Цена одной единицы продукции А и В составляет $20 и $50 соответственно. Как руководству составить оптимальную структуру производства компании?

Задача 14. Компания имеет возможность рекламировать свою продукцию по местному радио и телевидению. Бюджет на рекламу ограничен $10 000 в месяц. Одна минут рекламного времени на радио стоит $15, а на телевидении – $300. Компания предполагает, что реклама на радио по времени должна превышать рекламу на телевидении не менее чем в 2 раза. Вместе с тем известно, что нерационально использовать более 400 минут рекламы на радио в месяц. Последние исследования показали, что реклама на телевидении в 25 раз эффективнее рекламы на радио.

Как оптимальным образом спланировать рекламу?

Задача 15. Компания Woodco производит столы и стулья, которые делаются из дуба и из сосны. Компания имеет в своем распоряжении 150 кв. м. дуба и 210 кв. м. сосны. Для производства одного стола требуется 17 кв.м. дуба и 30 кв.м. сосны. Для производства одного стула необходимо 5 кв.м. дуба и 13 кв.м. сосны. Стоимость одного стола $40, одного стула – $15. Требуется определить: каким образом компания Woodco может максимизировать свою прибыль.

Задача 16. Компания Bloomington Brewery производит пиво и эль. Пиво продается по цене $5 за декалитр, а эль – $2. Для производства одного декалитра пива необходимо 5 кг. зерна и 2 кг. хмеля, а для производства эля – 2 кг. зерна и 1 кг хмеля. В распоряжении компании имеется 60 кг. зерна и 25 кг. хмеля. Необходимо определить каким образом компания может увеличить свою прибыль.

Задача 17. Завод бытовой химии производит 2 вида чистящих средств, А и В, используя при этом сырье 1 и 2. Обработка одной единицы сырья 1 стоит $8, в результате производится 0,5 единицы средства А и столько же средства В. Обработка одной единицы сырья 2 стоит $5, в результате получается 0,6 единиц средства А и 0,4 единицы средства В. Ежедневное производство средства А должно быть не менее 10 и не более 15 единиц. Аналогичные ограничения для средства В составляют 12 и 20 единиц.

Как наилучшим образом спланировать выпуск чистящих средств?

Задача 18. Предприятие электронной промышленности выпускает две модели приемников, причем каждая модель производится на отдельной технологической линии. Суточный объем производства на первой линии – 60 изделий, на второй линии – 75 изделий. На радиоприемник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприемник второй модели – 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыль от реализации одного радиоприемника первой и второй моделей равна 30 и 20 долларов, соответственно. Необходимо определить оптимальный суточный производственный план.

Задача 19. Промышленная компания выпускает два вида изделий. Производство каждого изделия состоит из последовательного выполнения трех операций. Время использования этих операций для производства данных изделий ограничено 10-ю часами в сутки. Время обработки и прибыль от продажи одного изделия каждого вида приведены в таблице 2.2.7. Найти оптимальный объем производства изделий каждого вида.

Таблица 2.2.7 Время обработки и прибыль от продажи одного изделия

Задача 20. Небольшая фирма выпускает два типа автомобильных деталей (А и В). Для этого она закупает литье, которое подвергается токарной обработке, сверловке и шлифовке. Данные, характеризующие производительность станочного парка фирмы, приведены в таблице 2.2.8.

Таблица 2.2.8 Производительность станков

Каждая отливка, из которой изготавливается деталь А, стоит $2. Стоимость отливки для детали В – $3. Продажные цены деталей равны, 5 и 6 долларам соответственно. Стоимость часа станочного времени составляет 20, 14 и 17,5 долларов, соответственно типу станка, эти расходы считаются фиксированными – они ограничены $7000 в месяц и не включаются в прибыль. Фирма работает по обычному графику: 8 часовой рабочий день, 5 рабочих дней в неделю. Спрос на деталь В практически неограничен, а на деталь А поступает не более 900 заказов в месяц. Менеджеру по производству необходимо определить, как наилучшим образом спланировать производственный процесс.

Задача 21. Компания MarCo, занимающаяся проведением маркетинговых исследований, планирует проведение нового исследования с помощью телефонного опроса. Для проведения исследования компании требуется опросить, по крайней мере, 150 замужних женщин, 120 женатых мужчин, а также 100 мужчин и 110 женщин, не находящихся в браке. Звонок в дневное время стоит $2, а звонок в вечернее время – $5. В таблице 2.2.9 приведены характеристики опросов, основанные на опыте предыдущих исследований.

Таблица 2.2.9 Оценочные результаты телефонного опроса

Так, например, на 30% звонков в дневное время отвечают замужние женщины, а на 15% звонков в вечернее время – одинокие мужчины. Так как штат сотрудников компании ограничен, то, по крайней мере, половина звонков должна быть сделана в вечернее время. Требуется определить: каким образом компании следует наилучшим образом спланировать маркетинговое исследование.

Задача 22. Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет чистый доход в 2,5 руб., один бычок – 5 тыс. руб. Как наилучшим образом использовать лесничеству свободную землю?

Задача 23. Исследовательская компания D&L Social Engineering планирует проведение маркетингового опроса. Для проведения опроса руководители компании рассматривают возможность привлечения студентов факультета социологии. Привлечение одного студента обходится компании в $1000, зарплата и прочие расходы в расчете на одного штатного сотрудника составляют $2000. В то же время, по опыту прошлых исследований, известно, что использование в исследовании более 75% студентов от общего числа исполнителей проекта нецелесообразно, так как качество их работы хуже. Кроме того, каждый штатный сотрудник может провести и обработать 8 интервью, а студент – только 6. Для координации работы на каждых 3 студентов выделяется 1 координатор, для штатных сотрудников требуется 1 координатор на 6 человек, всего компания имеет возможность привлечь к работе над проектом не более 10 координаторов (зарплата координаторов не входит в бюджет исследования). Бюджет исследования ограничен $60 000. Руководство компании полагая, что увеличение количества интервью повышает достоверность исследования, хотело бы определить оптимальный состав исполнителей исследования.

2.2.9. Самостоятельная работа студентов

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: