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

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

Линейное программирование — это раздел математики, занимающийся решением таких задач на отыскание наибольших и наименьших значений, для которых методы математического анализа оказываются непригодными. Другими словами термин «линейное программирование» характеризует определение программы (плана) работы конкретного экономического объекта на основе выявления линейных связей между его элементами. Задачей линейного программирования является нахождение оптимального, т. е. наилучшего, плана при заданной системе налагаемых на решение ограничений.

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

нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);

оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);

определение оптимального рациона (оптимизация состава химической смеси);

транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);

задача о размещении производства (планирование с учётом затрат на производство и транспортировку продукции);

задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

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

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется три исходных продуктаS1,S2 иS3. Расходы продуктов и запасы этих продуктов на складе приведены в таблице:

Источник

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

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

Линейное программирование – метод решения задач оптимизации.

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

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

Функция цели в задаче линейного программирования обычно записывается так:

.

Или в сокращённом виде с сигмой:

.

Можно встретить обозначение целевой функции и через C, и через F.

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

.

Или в сокращённом виде:

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

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

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

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

Множество чисел (запись последовательности иксов), удовлетворяющих системе ограничений, называется решением этой системы. Решение системы также часто называется планом, и немного реже – программой, но именно отсюда и пошло название «линейное программирование».

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

Решение задачи линейного программирования называется вырожденным, если в нём некоторые переменные равны нулю. В противном случае решение является невырожденным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 2. Схема задачи о смесях.

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

Требуется найти наиболее дешёвый набор из доступных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в свойм составе n различных компонент в определённых количествах, а сами компоненты являются составными частями m исходных материалов. Для упрощения примем, что n=3 и m=4. Пусть стоимость одной единицы материала соответственно составляет , , , . В свою очередь необходимое количество каждой из компонент в смеси составляет соответственно , , .

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

Виды материалов	Цена единицы материала	Количество компонент в материале
		K 1	K 2	K 3
1
2
3
4
Необходимое количество компонент

Запишем задачу в виде математических соотношений. Обозначим через x i количество материалов i-го вида, входящего в смесь. Тогда задача сведётся к отысканию минимума функции

Одним из частных случаев общей задачи о смесях служит задача о питании. К ней сейчас же и перейдём.

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

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

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

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

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

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

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

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

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

Пример 4. Схема задачи об использовании мощностей оборудования.

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

Мощность машин задана следующей таблицей:

Машины	П 1	П 2
A
B
C

В этой таблице — количество единиц продукции, производимое за единицу времени.

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

Машины	П 1	П 2
A
B
C

Машина A изготовлением продукции П 1 занята единицы времени на единицы продукции. Машина B изготовлением П 1 занята единицы времени по единицы продукции.

То есть получаем ещё одну систему:

Тогда общая стоимость всей продукции запишется в виде равенства:

.

Окончательно получаем систему ограничений, состоящую из соотношений:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные теоремы линейного программирования

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

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

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

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

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

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

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

Справедливость этого утверждения вытекает из теорем 2 и 4.

Итак, оптимум линейной формы нужно искать среди конечного числа допустимых базисных решений. Однако даже в простейших задачах линейного программирования (при небольших значениях m и n) нахождение оптимального решения путём рассмотрения всех базисных решений является крайне трудоёмким процессом, поскольку число базисных решений может быть весьма велико. Поэтому нужна какая-то вычислительная схема, позволяющая осуществлять переход от одного допустимого базисного решения к другому, при котором линейная форма или приблизилась к оптимуму, или, по крайней мере не изменила своего значения. Такой вычислительной схемой является, например, симплекс-метод решения задач линейного программирования.

Источник