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

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

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

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

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

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

Действительно, пусть необходимо исследовать на экстремум линейную функцию:

,

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

.

Необходимым условием экстремума является:

.

Но:

.

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

2. Формы записи ЗЛП, их эквивалентность. Преобразование ЗЛП к канонической форме

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

1) Общая, или произвольная, форма записи:

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

- произвольные .

2) Симметричная, или стандартная, форма записи:

3) Каноническая, или основная, форма записи:

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

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

Ограничения-неравенства:

()

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

( ).

3. Геометрическая интерпретация и графическое решение ЗЛП

Задача с двумя переменными.

Пусть требуется найти решение , доставляющее:

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

Начнем с геометрической интерпретации области допустимых решений.

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

Рис. 1

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

Если построить на одном рисунке область допустимых решений, вектор и одну из линий уровня, например, Z=0, то задача сводится к определению в области допустимых решений точки в направлении вектора , через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции Z. Это и есть графический способ решения ЗЛП. Если задача разрешима, могут представиться следующие случаи: задача имеет единственное решение (рис. 2,а); задача имеет бесконечное множество - альтернативный оптимум (рис. 2,б); целевая функция не ограничена; область допустимых решений - единственная точка, задача не имеет решения.

Рис. 2

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

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

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

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

,

.

Введя дополнительные переменные , приведем ЗЛП к канонической форме:

,

.

Предпочтительными являются переменные , их выбираем в качестве базисных. Свободные переменные . Их приравниваем нулю. Таким образом, начальный опорный план:, .

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

Таблица 1

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

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

Рассмотрим переход к нехудшему опорному плану.

1) Среди отрицательных оценок индексной строки выбирают максимальную по абсолютной величине (для данной задачи это -4), которая указывает на разрешающий столбец. Если задача решается на минимум, то разрешающий столбец выбирается по максимальной положительной оценке. Разрешающий столбец указывает на переменную, выводимую из базиса.

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

3) Элемент , стоящий на пересечении разрешающего столбца и строки, называется разрешающим.

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

- разрешающий элемент заменяется обратной величиной;

- остальные элементы разрешающей строки делятся на разрешающий элемент;

- остальные элементы разрешающего столбца делятся на разрешающий элемент и меняются знаки;

- прочие элементы вычисляются по правилу прямоугольника:

,

где - элемент, стоящий на пересечении -ой строки и разрешающего столбца, - элемент, стоящий на пересечении разрешающей строки и -го столбца.

Таблица 2

X1=(0;8;4;0;12);Z(X1)=32

Таблица 3

X2=(4;8;0;0;4);Z(X2)=40

Замечания:

1) если в индексной строке последней симплексной таблицы (содержащей оптимальный план) имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное множество оптимальных планов (альтернативный оптимум);

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

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

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

..

Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована так.

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

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

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

1) если прямая задача решается на максимум, то двойственная - на минимум, и наоборот;

2) в задаче на максимум ограничения - неравенства имеют знак «», а в задаче минимизации - «»;

3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;

4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;

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

6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается ограничение-неравенство, если же нет, то как ограничение-равенство;

7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

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

линейный экстремум двойственность максимизация

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

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

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

Таблица 4

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

,

.

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

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

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