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

Размещено на http://www.allbest.ru/

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

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

Математическая постановка общей задачи ЛП имеет следующий вид.

Найти максимум (или минимум) линейной функции

(2.1)

от переменных удовлетворяющих линейным ограничениям в форме равенств или неравенств

(2.2)

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

(обычно записывают так: ). (2.3)

Договоримся о терминологии линейного программирования. Функция носит название целевой функции. Её коэффициенты образуют вектор называемый целевым вектором. Любой вектор координаты которого удовлетворяют условиям (2.2), (2.3), называется допустимым планом (допустимым вектором, допустимой точкой) задачи линейного программирования. Все они образуют множество допустимых планов задачи. План доставляющий целевой функции наибольшее (или наименьшее) значение, называется оптимальным планом задачи ЛП. Ограничения (2.2) будем называть основными ограничениями, правая их часть - вектор - называется вектором ограничений или вектором ресурсов (запасов). Коэффициенты левых частей основных ограничений составляют матрицу , которую мы будем называть технологической матрицей.

2. Примеры моделей ЛП

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

Задача о производстве красок. Небольшая фабрика изготовляет два вида красок: INT для внутренних работ и EXT - для наружных работ. В производстве красок используются два исходных продукта А и В. Из-за малой площади склада максимально возможные суточные запасы этих продуктов равны 6 т. и 8 т. соответственно. На производство 1 т. краски INT расходуется 1 т. продукта А и 2 т. продукта В, а на изготовление 1 т. краски EXT идет 2 т. продукта А и 1 т. продукта В. Фабрика продает краску по цене 3 тыс. дол. за тонну краски INT и 2 тыс. дол. за тонну краски EXT. Исходные данные удобно свести в таблицу.

Изучение рынка сбыта показало, что суточный спрос на краску EXT никогда не превышает спрос на краску INT, более чем на 1 т. Какое количество краски каждого вида должна производить фабрика в сутки, чтобы доход от реализации продукции был максимален?

Построим математическую модель задачи. Для этого надо определить переменные задачи, целевую функцию и ограничения, которым удовлетворяют переменные. Обозначим через планируемый суточный объем производства краски INT, а через суточный объем производства краски EXT. Целевая функция будет выражать суточный доход от продажи краски, равный (тыс. долл.). Этот доход подлежит максимизации.

Построим ограничения задачи, связанные с ограниченными запасами продуктов А и В. На производство краски INT в количестве (т) будет использовано (т) продукта А, а на производство краски EXT в объеме (т) будет затрачено (т) продукта А. Поскольку суточный запас продукта А равен 6 т., то расход продукта А на изготовление красок двух видов не может превышать в сутки этой величины: Аналогично получим ограничение, связанное с запасом продукта В: Ограничение по соотношению спроса на краски можно описать неравенством: Учитывая естественные условия неотрицательности объемов выпуска продукции, окончательно получим следующую задачу линейного программирования:

Задача о рационе. Фермер для кормления скота зимой использует смесь из сена и силоса. Содержание питательных веществ в сене и силосе, их суточная норма в рационе и стоимость 1 кг кормов отражены в таблице:

Сколько килограммов сена и силоса надо взять для приготовления корма на одни сутки, чтобы он содержал все питательные вещества не ниже требуемой нормы и при этом был самым дешевым?

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

- по веществу :

- по веществу :

- по веществу :

При этом переменные не могут принимать отрицательные значения:

3. Различные формы записи задачи ЛП

Кроме развернутого представления задачи ЛП в виде (2.1) - (2.3) применяются и другие формы ее записи.

Используя знаки суммирования, задачу ЛП можно представить в координатной форме:

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

где - план задачи ЛП, - целевой вектор, - вектор запасов, - технологическая матрица.

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

4. Задачи ЛП в канонической и стандартной формах

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

Каноническая задача ЛП формулируется следующим образом. Требуется найти максимум линейной функции

 (2.4)

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

(2.5)

. (2.6)

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

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

Стандартная задача ЛП отличается от канонической только типом основных ограничений. Все они должны иметь форму неравенств »«: найти максимум линейной функции

(2.7)

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

(2.8)

. (2.9)

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

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

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

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

5. Эквивалентные преобразования задач ЛП

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

Ограничение-неравенство сводится к ограничению вида »« умножением на» - 1»:

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

(2.10)

Очевидно, что Условие (2.10) можно переписать в форме канонического ограничения-равенства Другими словами, ограничение-неравенство вида »« сводится к равенству путем добавления в левую часть новой (дополнительной) неотрицательной переменной.

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

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

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

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

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

Напомним, что от операции минимизации к операции максимизации (и наоборот) переходят умножением целевой функции на «- 1».

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

6. Экономическая интерпретация стандартной задачи ЛП

Пусть фирма располагает видами ресурсов (сырье, финансы, трудозатраты и т.д.) и планирует организовать выпуск из них видов продукции Известны следующие исходные данные: - затраты ресурса на выпуск одной единицы продукта (удельные затраты ресурсов); - прибыль от реализации одной единицы продукта (удельная прибыль); - запас ресурса

Требуется составить план выпуска продуктов из имеющихся ресурсов , при котором суммарная прибыль будет максимальна.

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

программирование неотрицательность доход производство

Согласно условиям задачи, она подлежит максимизации.

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

Учитывая естественные условия неотрицательности объемов выпуска продукции , придем к постановке стандартной задачи ЛП.

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

Приведем теперь эту задачу к канонической форме, добавив в правую часть каждого i-го неравенства неотрицательную переменную ():

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

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

Размещено на Allbest.ru