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

Введение

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

1. В которых требуется сделать выбор самого лучшего решения из набора допустимых.
2. В которых возможно выражать решение в виде набора величин каких-либо переменных.
3. В которых допустимые границы, заданные для области решений специальными параметрами задачи, определяются как линейные уравнения или неравенства.
4. В которых целевая функция определяется в формате линейных функций главных переменных. Основными критериями оптимальности найденного решения служат определяемые величины целевой функции, которые дают возможность сопоставить разные решения.

Статья: Задача линейного программирования

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

Для осуществления на практике решения задачи из области экономики методиками математики, надо сначала описать её в форме выражений математики. То есть в виде уравнения, неравенства и так далее, что означает построение экономической модели в математической форме. Учитывая указанные выше параметры задач линейного программирования, можно сформировать такую обобщённую последовательность построения модели:

1. Нужно выбрать определённое количество переменных величин, выбором численных величин которых чётко и ясно описывается какое-либо состояние из набора допустимых выбранного явления.
2. Необходимо выразить взаимные связи, которыми обладает исследуемое явление, в форме математических выражений. Они будут отражать набор ограничений поставленной задачи.
3. Следует определить числовую формулировку заданного критерия оптимальности в формате целевой функции.
4. Необходимо выполнить математическую формулировку задачи в виде задачи поиска максимального или минимального значения целевой функции, соблюдая все ограничения, наложенные на переменные.

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

Линейным программированием является подраздел теории математического программирования, который изучает проблемы определения решений, сформулированные в виде задач определения экстремума какой-либо целевой функции, с учётом всех ограничений на базовые переменные. Приведём некоторые примеры практических задач, формулируемых как задачи линейного программирования.

Рассмотрим пример формирования оптимального плана производства. На кондитерской фабрике выпускается два вида продукции, а именно конфеты и шоколад. Для выпуска этих продовольственных товаров необходимы сахар и какао-бобы. Чтобы произвести одну тонну продуктов каждого типа, необходимо иметь две тонны сахара. Чтобы сделать одну тонну шоколада, нужно пять тонн какао, а для выпуска тонны конфет нужно две тонны какао. Каждые сутки ресурсные запасы исходных составляющих равняются четыре и десять тонн соответственно. Если продать одну тонну шоколада, то прибыль будет пять тысяч рублей, а при продаже тонны конфет прибыль будет три тысячи рублей. Необходимо сформировать математическую модель, которая позволит найти суточный план выпуска продукции, обеспечивающий максимальную прибыль. Исходные параметры задачи представлены таблицей

ниже:

Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ

• $х_1$ - ежесуточное производство шоколада,
• $х_2$ - ежесуточное производство конфет.

Выберем целевую функцию. Суммарная прибыль от продажи суточной выработки $х = (х_1, х_2)$ будет определяться линейной функцией

z$ = 5 х_1 + 3 х_2$

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

1. На расходование запасов сахара

   $х_1 + х_2$

2. На расходование запасов какао-бобов

   $5 х_1 + 2 х_2$

3. Ограничения на знаки переменных

   $х_1 > 0, х_2 > 0$.

В финале получаем следующее выражение для этой задачи:

$max z = max (5 х_1 + 3 х_2)$

При условии соблюдения этих ограничений:

$х_1 + х_2$

$5 х_1 + 2 х_2$

$х_1 > 0, х_2 > 0$.

В следующем примере рассмотрим создание смеси с самой маленькой себестоимостью.

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

Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ

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

В качестве переменных возьмём:

• $х_1$ необходимый ресурс кукурузной муки, который используется для изготовления пищевых добавок в течение одного дня.
• $x_2$ необходимый ресурс соевой муки, который используется для изготовления пищевых добавок в течение одного дня.

Целевую функцию будет сформулирована так: необходимо обеспечить минимум суммарной стоимости пищевых добавок, вычислить которую возможно при помощи линейной функции

$z = 0,3 х_1 + 0,9 x_2$

При этом нужно выдержать следующие граничные условия:

1. Ограничение на объём выпускаемой смеси

   $х_1 + х_2 > 800$;

2. Ограничение на объём белка в пищевой добавке

   $0,09 х_1 + 0,6 x_2 > 0,3 (х_1 + x_2)$;

3. Ограничение на объём клетчатки в пищевой добавке

   $0,02 х_1 + 0,06 x_2$

4. Ограничение на допустимый знак переменных

   $х_1 > 0, x2 > 0$.

В окончательном виде после необходимых преобразований получим выражение:

$min z = min (0,3 х_1 + 0,9 x_2)$

при граничных условиях:

• $х_1 + x_2 > 800$;
• $0,21 х_1 – 0,3 x_2$
• $0,03 х_1 – 0,01 x_2 > 0$;
• $х_1 > 0, x_2 > 0$.