Мукомольный комбинат реализует муку двумя способами

Расчет экономико-математической модели при нелинейных реализациях продукции.

Рассмотрим применение выше приведенных методов на примере решения задачи оптимальной реализации продукции.

Пример 41. Мукомольный комбинат реализует муку двумя способами: в розницу через магазин и оптом через торговых агентов. При продаже х₁кг муки через магазин расходы на реализацию составляют х₁ 2 ден. ед., а при продаже х₂кг муки посредством торговых агентов — х₂ 2 ден. ед.

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

Решение.Составим математическую модель задачи. Найдем минимум суммарных расходов L = х₁ 2 + х₂ 2 при ограничениях: х₁ + х₂= 5 000, х_1,х₂≥0.

Для расчета модели используем метод множителей Лагранжа. Составим функцию Лагранжа

.

Найдем частные производные функции F по х₁, х₂ и λ, приравняем их к нулю, получим систему уравнений

откуда λ = -5 000, х₁ = 2 500, х₂ = 2 500, L = 12 500 000 ден. ед.

Давая х₁значения больше и меньше 2500, находим L и из определения экстремума функции получаем, что L при х₁ = х₂ = 2 500 достигает минимума.

Таким образом, для получения минимальных расходов необходимо расходовать в сутки через магазин и торговых агентов по 2 500 кг муки, при этом расходы на реализацию составят 12 500 000 ден. ед.

Дробно-линейное программирование

Математическая модель задачи

Дробно-линейное программирование относится к нелинейному программированию, так как имеет целевую функцию, заданную в нелинейном виде.

Задача дробно-линейного программирования в общем виде записывается следующим образом:

(54)

при ограничениях: x_j≥0, i=1,…,m, j=1,…n, (55)

где с_j, d_j,b_j, a_ij — постоянные коэффициенты и

Рассмотрим задачу дробно-линейного программирования в виде

(56)

(57)

Будем считать, что ≠0. Для решения этой задачи найдем область допустимых решений, определяемую ограничениями. Пусть эта область не является пустым множеством.

Прямая х₂=кх₁проходит через начало координат. При некотором фиксированном значении L угловой коэффициент к прямой тоже фиксирован и прямая займет определенное положение. При изменении значений L прямая х₂ = кх₁ будет поворачиваться вокруг начала координат.

Установим, как будет вести себя угловой коэффициент к при монотонном возрастании L. Найдем производную от к по L:

(58)

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоянный знак и при увеличении L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если угловой коэффициент прямой имеет положительное значение, то прямая вращается против часовой стрелки, при отрицательном значении к — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность задачи.

При этом возможны следующие случаи.

1. Область допустимых решений ограничена, максимум и минимум достигаются в ее угловых точках (рис. 27а).

2. Область допустимых решений неограничена, однако существуют угловые точки, в которых целевая функция принимает максимальное и минимальное значения (рис. 27б).

3. Область допустимых решений неограниченна, имеется один из экстремумов. Например, минимум достигается в одной из вершин области и имеет так называемый, асимптотический максимум (рис. 27в).

4.

a)

Область допустимых решений неограниченна. Максимум и минимум являются асимптотическими (рис. 27г).

Рисунок 27

Алгоритм решения.

1.Находим область допустимых решений.

2.Определяем угловой коэффициент к и устанавливаем направление поворота целевой функции.

3.Находим точку max(min) целевой функции или устанавливаем неразрешимость задачи.

Источник

28.4.2. Расчет экономико-математической модели при нелинейных реализациях продукции

Рассмотрим применение выше приведенных методов на примере решения задачи оптимальной реализации продукции.

Пример 9. Мукомольный комбинат реализует муку двумя способами: в розницу через магазин и оптом через торговых агентов. При продаже X1 кг муки через магазин расходы на реализацию составляют Х12 ден. ед., а при продаже X2 кг муки посредством торговых агентов — Х22 ден. ед.

Определить, сколько килограммов муки следует продавать каждым способом, чтобы затраты на реализацию были мини­мальными, если в сутки выделяется для продажи 5 000 кг муки.

Решение. Составим математическую модель задачи.

Найдем минимум суммарных расходов

Для расчета модели используем метод множителей Лагранжа. Составим функцию Лагранжа

Найдем частные производные функции F по X1, X2 и λ, приравняем их к нулю, получим систему уравнений

Откуда λ = -5 000, X1 = 2 500, X2 = 2 500, L = 12 500 000 ден. ед.

Давая Х1 значения больше и меньше 2500, находим L и из определения экстремума функции получаем, что L при Х1 = X2 = 2 500 достигает минимума.

Таким образом, для получения минимальных расходов не­обходимо расходовать в сутки через магазин и торговых аген­тов по 2 500 кг муки, при этом расходы на реализацию составят 12 500 000 ден. ед.

Источник

Лабораторная работа №12: Нахождение решения задач нелинейного программирования (метод множителей Лагранжа)

Цель работы:

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

Рекомендации по решению:

1. При решении задач нелинейного программирования средствами Microsoft Excel используется надстройка Поиск решения, которая позволяет найти оптимальные решения.

2. При решении задач линейного программирования средствами MathCad с помощью встроенной функции Maximize (в случае поиска максимума функции) или Minimize (в случае поиска минимума функции).

Задание к лабораторной работе:

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

Мукомольный комбинат реализует муку двумя способами: в розницу через магазин и оптом через торговых агентов. При продаже х _<кг муки через магазин расходы на реализацию составляют ден. ед., а при продаже x₂ кг муки посредством торговых агентов — ден. ед. Определить, сколько кг муки следует продавать каждым способом, чтобы затраты на реализацию были минимальными, если в сутки для продажи выделяется 5000 кг муки.

Решение. Составим математическую модель задачи. Найдем минимум суммарных расходов

Для расчета модели используем метод множителей Лагранжа. Составим функцию Лагранжа.

Найдем частные производные функции F по х₁, х₂ и λ, приравняем к нулю, получим систему уравнений:

Из первого и второго уравнений имеем x₁ – x₂ =0.

Решая это уравнение совместно с третьим, имеем λ = -5000, х₁ = 2500, х₂ = 2500, L=12 500 тыс. ден. ед. Давая х₁ значения больше и меньше 2500 находим L и из определения экстремума функции получаем, что L при х₁ = х₂ = 2500 достигает ми­нимума.

Ответ. Для получения минимальных расходов необходимо расходо­вать в сутки через магазин и торговых агентов по 2500 кг муки, при этом расходы на реализацию составят 12 500 тыс. ден. ед.

Источник

Дробно-линейное программирование

Математическая модель задачи

Дробно-линейное программирование относится к нелиней­ному программированию, так как имеет целевую функцию, за­данную в нелинейном виде.

Задача дробно-линейного программирования в общем виде записывается следующим образом:

где c_j, d_j, b_i, a_ij — постоянные коэффициенты и d_jx_j ≠0.

Рассмотрим задачу дробно-линейного программирования в виде

(1.1)

(1.2)

Для решения этой задачи найдем область допустимых ре­шений, определяемую ограничениями (1.2). Пусть эта область не является пустым множеством.

Из выражения (1.1) найдем х₂:

Прямая x₂ = kx₁ проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное поло­жение. При изменении значений L прямая х₂ = kx₁ будет по­ворачиваться вокруг начала координат (рис. 1.6).

Рис. 1.6

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдем производную от k по L:

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоян­ный знак и при увеличении L угловой коэффициент будет толь­ко возрастать или только убывать, а прямая будет поворачи­ваться в одну сторону. Если угловой коэффициент прямой име­ет положительное значение, то прямая вращается против ча­совой стрелки, при отрицательном значении k — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность за­дачи.

При этом возможны следующие случаи.

1. Область допустимых решений ограничена, максимум и минимум достигаются в ее угловых точках (рис. 1.7).

2. Область допустимых решений неограничена, однако су­ществуют угловые точки, в которых целевая функ­ция принимает максимальное и минимальное значения (рис. 1.8).

3. Область допустимых решений неограничена, имеется один из экстремумов. Например, минимум достигает­ся в одной из вершин области и имеет так называемый асимптотический максимум (рис. 1.9).

4. Область допустимых решений неограничена. Максимум и минимум являются асимптотическими (рис. 1.10).

1. Находим область допустимых решений.

2. Определяем угловой коэффициент k и устанавливаем на­правление поворота целевой функции.

3. Находим точку max(min) целевой функции или устана­вливаем неразрешимость задачи.

Экономическая интерпретация задач дробно-линейного программирования

Математическая модель задачи дробно-линейного програм­мирования может быть использована для определения рента­бельности затрат на производство изделий, рентабельности продаж, затрат в расчете на рубль выпускаемой продукции, себестоимости изделий.

Обозначим: r_j — прибыль предприятия от реализации еди­ницы изделия j-гo вида;

x_j — количество выпущенной продукции j-гo вида;

s_j — цена единицы продукции j-гo вида;

c_j — себестоимость производства единицы изделия j-гoвида;

d_j — затраты на производство одного изделия j-гo вида.

Задача рентабельности (Р_з) затрат на производство изде­лий имеет вид

Задача рентабельности (Р_n) продаж имеет вид

Задача определения затрат (З_р) в расчете на рубль товар­ной продукции записывается в виде

Задача нахождения себестоимости изделия записывается как

Указанные математические модели имеют системы ограниче­ний в зависимости от условий задачи.

Применение дробно-линейного программирования для определения себестоимости изделий

Рассмотрим использование дробно-линейного программи­рования для нахождении себестоимости изделий.

Пример 6. Для производства двух видов изделий А и В пред­приятие использует три типа технологического оборудования. Каждое из изделий должно пройти обработку на каждом из типов оборудования. Время обработки каждого из изделий, затраты, связанные с производством одного изделия, даны в табл. 1.1

Оборудование I и III типов предприятие может использо­вать не более 26 и 39 ч соответственно, оборудование II типа целесообразно использовать не менее 4 ч.

Определить, сколько изделий каждого вида следует изго­товить предприятию, чтобы средняя себестоимость одного из­делия была минимальной.

Таблица 1.1

Решение. Составим математическую модель задачи. Пусть x₁ — количество изделий вида А, которое следует из­готовить предприятию, x₂ — количество изделий вида В. Об­щие затраты на их производство составят (2х₁ + 3x₂) тыс. р., а средняя себестоимость одного изделия будет равна

Математическая модель задачи примет вид

ΔАВС — область допустимых решений (рис. 1.11).

Рис. 1.11

Угловой коэффициент прямой равен k = (L — 2)/(3 — l), тогда

Так как dk/dL > 0, то функция k = (L — 2)/(3 — L) возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С (рис. 1.11) целевая функция будет иметь наименьшее значение (глобальный минимум).

Найдем координаты точки С. Решая систему

получим С (3, 1), _опт = (3, 1), L =9/4.

Следовательно, предприятию следует выпускать 3 изделия вида А и 1 изделие вида В. При этом средняя себестоимость одного изделия будет минимальной и равной 2,25 тыс. р.

Сведение экономико-математической модели дробно-линейного программирования к задаче линейного программирования

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

Тогда задача примет вид

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

Пример 7. Дана задача дробно-линейного программирования

Преобразуем систему ограничений, умножив обе части всех ограничений на у₀, и перейдем к переменным у₀, y₁, y₂, y₃, y₄. Задача примет вид

Таблица 1.2

Получили задачу линейного программирования, решаем ее симплексным методом (табл. 1.2).

Ответ: _опт = (2, 0, 0, 2), L_max = 4/3.

Метод множителей Лагранжа

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

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

Для решения задачи составляется функция Лагранжа

где λ_i — множители Лагранжа.

Затем определяются частные производные:

Приравняв к нулю частные производные, получим систему

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

Пример 8. Найти точку условного экстремума функции

Решение. Составим функцию Лагранжа

Найдем частные производные функции Лагранжа по пере­менным x₁, x₂, x₃, λ₁, λ₂. Приравняв к нулю полученные вы­ражения, решим систему

Определим характер экстремума, изменяя полученные зна­чения переменных. Измененные значения должны удовлетво­рять заданной системе ограничений. Возьмем х₁ > -2, напри­мер x₁ = -1, тогда из системы ограничений получим х₂ = -3, x₃ = 7/2, L = -15/2. Возьмем х₁ 2 ден. ед., а при продаже x₂ кг муки посредством торговых агентов — х₂ 2 ден. ед.

Определить, сколько килограммов муки следует продавать каждым способом, чтобы затраты на реализацию были мини­мальными, если в сутки выделяется для продажи 5 000 кг муки.

Решение. Составим математическую модель задачи.

Найдем минимум суммарных расходов

Для расчета модели используем метод множителей Лагранжа. Составим функцию Лагранжа

Найдем частные производные функции F по x₁, x₂ и λ, приравняем их к нулю, получим систему уравнений

откуда λ = -5 000, x₁ = 2 500, x₂ = 2 500, L = 12 500 000 ден. ед.

Давая х₁ значения больше и меньше 2500, находим L и из определения экстремума функции получаем, что L при х₁ = x₂ = 2 500 достигает минимума.

Таким образом, для получения минимальных расходов не­обходимо расходовать в сутки через магазин и торговых аген­тов по 2 500 кг муки, при этом расходы на реализацию составят 12 500 000 ден. ед.

Источник