Графический способ решения ЗЛП

ЛинейноЕ программированиЕ

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

Основные понятия

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

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:

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

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

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

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

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

3) умение переходить к нехудшему опорному плану.

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

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

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

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

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

 

Дана система m уравнений и неравенств с n переменными

(2.1)

и линейная функция

. (2.2)

Необходимо найти такое решение системы (2.1) с неотрицательными компонентами , при котором линейная функция f принимает наибольшее (наименьшее) значение.

Систему (2.1) называют системой ограничений, функцию f — целевой функцией ограничений, поставленную задачу — общей задачей линейного программирования (ЛП).

Более кратко общую задачу ЛП можно записать следующим образом:

(2.3)

(2.4)

(2.5)

(2.6)

(2.7)

Задача ЛП называется стандартной, если система ограничений (2.3)–(2.7) содержит только неравенства, т. е. k = m.

Задача ЛП называется канонической или основной задачей ЛП, если система ограничений состоит только из равенств, т. е. k = 0и l = m.

Упорядоченный набор чисел , удовлетворяющий системе ограничений (2.4)–(2.7), называется допустимым решением или планом задачи.

Допустимое решение (план) задачи: , при котором целевая функция (2.3) принимает свое максимальное (минимальное) значение, называется оптимальным.

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

Так ограничение-неравенство можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной :

. (2.8)

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

В это же время каждое уравнение можно записать в виде системы неравенств:

(2.9)

Пример 2.1. Записать задачу, состоящую в минимизации функции , при условиях:

(2.10)

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

Вместо минимизации функции f рассматривается задача максимизации функции , при ограничениях, получающихся из ограничений (2.10), добавлением к левой части неравенств вида «£» и вычитанием из левой части неравенств вида «³» неотрицательной переменной. Таким образом получаем задачу:

;

Графический способ решения ЗЛП

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

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

, (2.11)

(2.12)

. (2.13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.12), (2.13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.11)–(2.13) есть выпуклое множество.

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

 

Рис. 2.1

 

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

Найдем частные производные целевой функции по и :

, (2.14)

. (2.15)

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

.

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

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

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

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

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

3. Проводим произвольную линию уровня .

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

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

Пример 2.2. Найти максимум функции ,

при ограничениях:

Строим прямую по двум точкам (), (). Она делит плоскость на две полуплоскости. Точка с координатами (0,0), удовлетворяет первому неравенству, поэтому данное неравенство определяет полуплоскость, содержащую начало координат. Аналогично определяем полуплоскости, задаваемые
остальными неравенствами. (На рис. 2.1 штриховка указывает ту полуплоскость, которая определяется данным неравенством.)

Далее построим линию уровня для и вектор-градиент

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

Координаты точки C определяются как решение системы

~

откуда .

.

Итак, максимальное значение целевой функции равно 24, достигается это значение при .

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

Теория двойственности

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

Математическая модель задачи:

, (2.26)

(2.27)

, . (2.28)

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

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

1) общую стоимость отходов сырья покупающая организация стремится минимизировать;

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

Эти требования формализуются в виде следующей ЗЛП.

Требование 1 покупающей организации — минимизация покупки:

. (2.29)

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

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

(2.30)

По смыслу задачи оценки не должны быть отрицательными:

(2.31)

Переменные , , называют двойственными или объективно обусловленными оценками.

Задачи (2.26)–(2.28) и (2.29)–(2.31) называют парой взаимно двойственных ЗЛП.

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

1.Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.

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

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

4.Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.

5.Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

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

7.Все переменные в обеих задачах неотрицательны.

 

Правила построения двойственных задач

Исходная задача	Двойственная задача
	— любого знака
— любого знака

 

Основные теоремы двойственности
и их экономическое содержание

Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т. е.:

(2.32)

— основное неравенство теории двойственности.

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

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

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

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

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

(2.33)

(2.34)

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

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

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

. (2.35)

Основные виды экономических задач,
сводящихся к ЗЛП

Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j, . Будем обозначать эту продукцию . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i, . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, — вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации , т. е. —вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i -го ресурса требуется для производства единицы продукции j -го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Так как — цена реализации единицы j -й продукции, цена реализованных единиц будет равна , а общий объем реализации . Это выражение — целевая функция, которую нужно максимизировать.

Так как — расход i -го ресурса на производство единиц j -й продукции, то, просуммировав расход i -горесурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить , единиц:

.

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

Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:

, (2.36)

при ограничениях:

, ; (2.37)

, . (2.38)

Так как переменные входят в функцию и систему ограничений только в первой степени, а показатели являются постоянными в планируемый период, то (2.36)–(2.38) — задача линейного программирования.

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

Пример 2.4. Для откорма животных используют три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в 1 кг. каждого вида комбикорма жиров, белков и углеводов (граммы) приведено в таблице:

 

Содержание в 1 кг	Комбикорм
А	В	С
Жиры
Белки
Углеводы
Стоимость 1 кг

 

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

Математическая модель задачи есть: — количество комбикорма А, В и С. Стоимость смеси есть:

Ограничения на количество ингредиентов:

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

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

Пример 2.5. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

 

Рабочие	Станки
С1	С2	С3	С4
Р1	2,3	1,9	2,2	2,7
Р2	1,8	2,2	2,0	1,8
Р3	2,5	2,0	2,2	3,0
Р4	2,0	2,4	2,4	2,8

 

Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?

Обозначим за — переменные, которые принимают значения 1, если i -й рабочий работает на j -м станке. Если данное условие не выполняется, то . Целевая функция есть:

Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть

Кроме того, каждый станок обслуживает только один рабочий:

Кроме того, все переменные должны быть целыми и неотрицательными: .

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

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

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

 

Ресурсы	Выпускаемая продукция	Объем ресурсов
	Трудовые ресурсы, чел.-ч
	Полуфабрикаты, кг
	Станочное оборудование, станко-ч
Цена единицы продукции, р.

Решение. Пусть – объемы продукции планируемой к выпуску;