- •Донецкий университет экономики и права
- •Экономико-математические методы и модели: оптимизационные методы и модели
- •Содержание
- •Введение
- •Тема 1 концептуальные аспекты математического моделирования экономики
- •1.1. Понятие модели. Классификация моделей
- •Тема 2 оптимизационные экономико-математические модели
- •2.1. Понятие оптимизационной модели
- •2.2. Примеры постановки оптимизационных задач
- •Вопросы для самоконтроля по темам 1, 2
- •Вопросы для самостоятельного изучения по темам 1, 2
- •Тема 3 задачи линейного программирования и методы их решения
- •3.1. Графический метод решения задач линейного программирования
- •3.2. Симплекс-метод решения задач линейного программирования
- •3.3. Метод искусственного базиса
- •3.4. Специальные случаи решения задач линейного программирования
- •Вопросы для самоконтроля по теме 3
- •Тема 4 теория двойственности и анализ линейных моделей оптимизационных задач
- •4.1. Понятие и экономический смысл двойственной задачи
- •4.2. Двойственный симплекс-метод
- •Вопросы для самоконтроля по теме 4
- •Вопросы для самостоятельного изучения по теме 4
- •Тема 5 целочисленное программирование
- •5.1. Понятие задачи целочисленного программирования
- •5.2. Метод отсекающих плоскостей (Гомори)
- •Вопросы для самоконтроля по теме 5
- •Вопросы для самостоятельного изучения по теме 5
- •Тема 6 нелинейное программирование
- •Вопросы для самостоятельного изучения по теме 6
- •Задания для индивидуальной работы студента
- •Задание 1
- •Задание 2
- •Задание 3
- •Задание 4
- •Питання до екзамену
- •Литература
- •Відповідальний за випуск: завідувач кафедри вищої математики та інформаційних технологій к.Ф-м.Н., доцент л.М. Харламова
- •83048, М. Донецьк, вул. Університетська, 77
2.2. Примеры постановки оптимизационных задач
Пример 2.1. Задача планирования производства
Для изготовления продукции двух типов (I, II) требуется четыре вида сырья S1, S2, S3, S4. На изготовление одной единицы каждого типа продукции требуется разное количество сырья. Запасы сырья ограничены. Прибыль от реализации одной единицы продукции каждого типа известна. Запасы сырья каждого вида, нормозатраты сырья на единицу каждого из типов продукции, а также прибыль от единицы производимой продукции представлены в таблице.
Таблица 2.1 – Исходные данные к примеру 2.1
Виды сырья |
Нормозатраты сырья на единицу продукции |
Запасы сырья |
|
I вид |
II вид |
||
S1 |
2 |
3 |
19 |
S2 |
2 |
1 |
13 |
S3 |
0 |
3 |
15 |
S4 |
3 |
0 |
18 |
Прибыль от реализации единицы продукции |
7 |
5 |
|
Необходимо определить, сколько продукции каждого вида нужно выпускать, чтобы максимизировать суммарную прибыль предприятия.
Для математического описания любой задачи оптимизации важно определить, что является переменными задачи и как через эти переменные можно выразить целевую функцию и систему ограничений.
В данном случае удобно обозначить: x1 – количество изготавливаемой продукции I типа, x2 – количество изготавливаемой продукции II типа.
Тогда прибыль от реализации продукции I типа составит 7x1, а от реализации второго типа – 5x1 (свойство пропорциональности). Совокупная прибыль предприятия составит 7x1 + 5x1 (свойство аддитивности). То есть целевая функция имеет вид:
z = 7x1 + 5x1 → max.
На выпуск единицы продукции первого типа требуется 2 единицы сырья S1 (см. табл. 2.1), тогда всего сырья S1 на выпуск x1 единиц продукции первого типа потребуется 2x1, на выпуск продукции второго типа – 3x2. Совокупный расход сырья S1 на выпуск продукции обоих типов составит 2x1 + 3x2, и он не должен превышать запаса этого ресурса в 19 единиц. Таким образом, имеем первое ограничение:
2x1 + 3x2 ≤ 19.
Аналогичным образом получаются остальные ограничения задачи:
2x1 + x2 ≤ 13,
3x2 ≤ 15,
3x1 ≤ 18.
Поскольку по смыслу задачи переменные x1 и x2 не могут быть отрицательными, водим ограничения на знак:
x1 ≥ 0, x2 ≥ 0.
Пример 2.2. Динамическая модель принятия решений
Компания производит лодки. Потребность в лодках в каждом квартале составляет: 40, 60, 75, 25. К началу первого квартала компания имеет запас в 10 лодок.
В течение каждого квартала компания может производить до 40 лодок, используя основное рабочее время, затрачивая 400 грн. на 1 лодку. Можно увеличить производство лодок выше 40, используя сверхурочное время, но тогда цена лодки составит 450 грн. Хранение нереализованного на конец квартала запаса лодок обходится компании в 20 грн. за 1 лодку.
Составить производственную программу, минимизирующую затраты на производство и хранение в течение 4 кварталов.
Введем переменные:
4 переменных xi – количество лодок, произведенных в j-м квартале в основное рабочее время;
4 переменных yi – количество лодок, произведенных в j-м квартале в сверхурочное время;
4 переменных hi – количество лодок, нереализованных на конец j-го квартала.
Целевая функция, минимизирующая затраты, имеет вид:
Ограничения по основным производственным мощностям:
ограничения, взаимоувязывающие производство, сбыт и складские запасы:
– запасы на конец первого квартала равны запасам на начало квартала (10) плюс производство в основное (x1) и сверхурочное (y1) время в первом квартале, минус объем реализации в первом квартале. Аналогично:
Оптимальным решением данной задачи будет: z = 78 450, , x4 = 25, y1 = 0, y2 = 10, y3 = 35, y4 = 0, h1 = 10, .
Пример 2.5. Задача на раскрой
Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов.
В этой и подобных задачах на раскрой необходимо составить таблицу возможных рациональных вариантов раскроя. В данном случае можно выделить следующие способы распила бревен:
Способ распила, i |
Число получаемых брусьев длиной, м |
||
1,2 |
3,0 |
5,0 |
|
1 |
5 |
- |
- |
2 |
2 |
1 |
- |
3 |
- |
2 |
- |
4 |
- |
- |
1 |
Заметим, что, в принципе, есть и другие варианты распила, например, 1 брус длиной 1,2 м и 1 брус длиной в 3 м, но этот способ не рациональный, поскольку явно хуже имеющегося второго способа. Подобного рода нерациональные способы не рассматриваем.
Обозначим: – число бревен, распиленных i-тым способом (i = 1,2,3,4); x – число комплектов брусьев (которое совпадает с количеством бревен по 3 м).
Учитывая, что все бревна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид:
x1 + x2 + x3 + x4 = 195 – все бревна должны быть распилены,
5x1 + 2x2 = 2x – количество брусьев длиной 1,2 м в 2 раза больше числа комплектов,
x2 + 2x3 = x – количество брусьев по 3 м равно числу комплектов,
x4 = 3x – количество брусьев по 5 м в три раза больше числа комплектов.
.
Часто в задачах на раскрой критерием принятия решения бывает минимизация отходов. Для записи такого критерия в таблице со способами раскроя нужно определить непродуктивные отходы для каждого способа. Для предыдущей задачи отходы для первого способа распила равны нулю, для второго способа – 0,6 м, для третьего – 0, для четвертого – 1 м.
Критерий минимизации отходов в этом случае можно было бы записать так:
.