"Чистая"
и прикладная математика

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Примеры формулировки задач линейного программирования

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

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

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

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

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

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

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

Примеры формулировки задачи линейного программирования

Разберём несколько типов экономических задач и запишем их в виде математических соотношений. Или, как мы недавно говорили, построим математическую модель предметной области.

Пример 1. Схема задачи использования сырья.

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

Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья - соответственно , , , единицы.

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

Решение. Для удобства сначала все данные запишем в виде таблицы:

Виды сырья Запасы сырья Виды продукции
Доход от реализации одной единицы продукции

Тогда на основании таблицы запишутся неравенства (ограничения):

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

Из остальных строк таблицы составим ещё 3 неравенства системы.

Доход от реализации единиц продукции по у. е. за каждую единицу составляет у. е. Аналогично доход от реализации единиц продукции по у. е. за каждую единицу составит у. е. Тогда суммарный доход от реализации двух видов продукции и запишется в виде . В задаче требуется найти максимальный доход, то есть найти максимум функции цели .

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

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

Нет времени вникать в решение? Можно заказать работу!


Пример 2. Схема задачи о питании.

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

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

Решение. Строим таблицу:

Питательные вещества Норма Продукты
Ж
Б
У
В
Стоимость питательных веществ

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

Запишем задачу в виде математических соотношений. В задаче неизвестно количество каждого вида продукта. Поэтому обозначим количество продукта буквой , количество продукта - буквой , количество продукта - буквой .

Получим систему неравенств (ограничений):

Требуется найти найти такое неотрицательное решение системы ограничений, при котором функция цели обращалась бы в минимум.

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


Пример 3. Транспортная задача (схема).

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

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

Составить такой план перевозок, чтобы общая стоимость всех перевозок была минимальной.

Решение. Считаем, что запас всего груза на обоих пунктах отправления равен потребности в этом грузе на всех трёх пунктах назначения, т. е.

Запишем задачу в виде математических соотношений. Количество единиц груза, отправляемых из пункта в пункт , обозначим и составим матрицу перевозок (таблицу):

Пункт отправления Пункт назначения Запас груза
Потребность в грузе

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

Тогда система ограничений запишется в виде уравнений:

Цель задачи - найти неотрицательное решение системы уравнений, при котором функция цели была минимальной.

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

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

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

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

Пример 4. Записать систему неравенств

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

Решение. Прибавляя к левым частям неравенств по одной дополнительной переменной, получим систему уравнений:

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

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

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

Нет времени вникать в решение? Можно заказать работу!

Продолжение темы "Линейное программирование"

Графический метод решения задач линейного программирования

Пример задачи линейного программирования: задача использования ресурсов, её графическое решение

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

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

Симплекс-метод: случай, когда максимум целевой функции - бесконечность

Симплекс-метод: случай, когда система не имеет ни одного решения

Симплекс-метод: случай, когда оптимальное решение - не единственное

Поделиться с друзьями