2 Задача линейного программирования и этапы ее решения графическим методом

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

Первая работа, в которой были разработаны методы линейного программирования, была написана в 1939 г. советским математиком-экономистом Л.В. Канторовичем и носила название «Математические методы организации и планирования производства». Именно ее появление открыло новый этап в применении математики в экономике. Через 10 лет американским математиком Дж. Данцингом был разработан важный и очень эффективный метод решения подобного типа задач - симплекс-метод. Сам же термин «линейное программирование» впервые появился в 1951 г. в работах Дж. Данцига и Т. Купманса.

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

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

В общем виде модель записывается следующим образом:

· целевая функция:

= c1x1 + c2x2 + ... + cnxn > max(min); (1.1)

· ограничения:

a11x1 + a12x2 + ... + a1nxn ? b1, a21x1 + a22x2 + ... + a2nxn ? b2,

...

am1x1 + am2x2 + ... + amnxn ? bm; (1.2)

· требование неотрицательности:

xj ? 0, (1.3)

При этом aij, bi, cj (, ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор , удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

= c1x1 + c2x2 + ... + cnxn > max(min);

a11x1 + a12x2 + ... + a1nxn = b1,

a21x1 + a22x2 + ... + a2nxn = b2,

...

am1x1 + am2x2 + ... + amnxn = bm;

xj ? 0,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

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

1. Задача об оптимальном использовании ресурсов при производственном планировании.

Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (, ). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей.

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

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

2. Задача о смесях (планирование состава продукции).

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

Пример задачи: На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля. Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.

3. Транспортная задача.

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

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

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

Пусть дана задача

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

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

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений задачи линейного программирования - непустое множество, например многоугольник (рисунок 1 [2, с. 29, рисунок 1.3] ).

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках NM целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (2.1) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня функции (линиями постоянного значения).

Рисунок 1

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

Частная производная (2.4) (2.5) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и скорости возрастания Z соответственно градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор -с указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямым Z = const семейства .

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

1. С учетом системы ограничений строим область допустимых решений.

2. Строим вектор наискорейшего возрастания целевой функции - вектор градиентного направления.

3. При решении задачи на максимум перемещаем линию уровня перемещают в антиградиентном направлении (на рисунке 1 - до точки ).

4. Определяем оптимальный план и экстремальное значение целевой функции .

Сделаем некоторые примечания:

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

2) Если область допустимых решений неограничена по направлению вектора , то сама целевая функция неограничена сверху в этой области, и тогда max Z = . Если область допустимых решений неограничена в направлении, противоположном c, то получаем min Z= .

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

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

В частном случае, когда в систему ограничений входят только две переменные x1 и x2, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x1, x2 ? 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.

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

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

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

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

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