Processing math: 100%
Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

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

Определение 1

Задача линейного программирования — это задача, которая решается методом поиска экстремума на многомерном векторном пространстве, заданном системой линейных уравнений и неравенств.

Введение

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

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

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

  1. Нужно выбрать определённое количество переменных величин, выбором численных величин которых чётко и ясно описывается какое-либо состояние из набора допустимых выбранного явления.
  2. Необходимо выразить взаимные связи, которыми обладает исследуемое явление, в форме математических выражений. Они будут отражать набор ограничений поставленной задачи.
  3. Следует определить числовую формулировку заданного критерия оптимальности в формате целевой функции.
  4. Необходимо выполнить математическую формулировку задачи в виде задачи поиска максимального или минимального значения целевой функции, соблюдая все ограничения, наложенные на переменные.
«Задача линейного программирования» 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Найди решение своей задачи среди 1 000 000 ответов
Найти

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

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

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

ниже:

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

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

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

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

z=5х1+3х2

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

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

    х1+х2

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

    5х1+2х2

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

    х1>0,х2>0.

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

maxz=max(5х1+3х2)

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

х1+х2

5х1+2х2

х1>0,х2>0.

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

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

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

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

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

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

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

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

z=0,3х1+0,9x2

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

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

    х1+х2>800;

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

    0,09х1+0,6x2>0,3(х1+x2);

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

    0,02х1+0,06x2

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

    х1>0,x2>0.

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

minz=min(0,3х1+0,9x2)

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

  • х1+x2>800;
  • 0,21х10,3x2
  • 0,03х10,01x2>0;
  • х1>0,x2>0.
Дата написания статьи: 02.03.2020
Найди решение своей задачи среди 1 000 000 ответов
Крупнейшая русскоязычная библиотека студенческих решенных задач
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot

Изучаешь тему "Задача линейного программирования"? Могу объяснить сложные моменты или помочь составить план для домашнего задания!

AI Assistant