Линейное программирование в принятии управленческих решений.

Предисловие

 

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

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

Учебное пособие может быть использовано различными категориями читателей. Студенты дневных отделений помимо изучения дисциплины «Теория и методы принятия управленческих решений» могут использовать учебное пособие в курсах «Исследование операций». «Теория оптимального управления», «Экономико-математическое моделирование» и др. Менеджерам, экономистам и инженерам, изучающим теорию принятия решений самостоятельно или в институтах или курсах повышения квалификации, пособие позволит познакомиться с ее ключевыми идеями.

Включенные в учебное пособие материалы будут полезны обучающимся по программам переподготовки, программам МБА, занимающимся по дистанционной форме образования и получающим второе высшее образование.

Линейное программирование в принятии управленческих решений.

 

1. Классификация экономических моделей.

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

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

По степени агрегирования объектов моделирования различают модели:

· микроэкономические;

· одно-, двухсекторные (одно-, двухпродуктовые);

· многосекторные (многопродуктовые);

· макроэкономические;

· глобальные.

По учету фактора времени различают модели:

 

· статические;

· динамические.

 

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

По цели создания и применения различают модели:

· балансовые;

· эконометрические;

· оптимизационные;

· сетевые;

· систем массового обслуживания;

· имитационные (экспертные).

 

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

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

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

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

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

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

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

По учету фактора неопределенности различают модели:

· детерминированные (с однозначно определенными результатами);

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

По типу математического аппарата различают модели:

· линейного и нелинейного программирования;

· корреляционно-регрессионные;

· матричные;

· сетевые;

· теории игр;

· теории массового обслуживания и т.д.

 

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

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

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

Этап 1. Под допустимым решением задачи ЛП понимается такой числовой набор значений искомых переменных, который при подстановке во все ограничения и граничные условия задачи обращает их в истинные числовые неравенства и равенства. Под областью допустимых решений (ОДР) задачи ЛП понимается геометрическое место точек, координаты которых являются допустимыми решениями.

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

0, 8 x₁ + 0, 5 x₂ = 400

Рис.3.1ОДР по молоку

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

Результаты этих вычислений:

x₁ = 0; x₂ = 800;

x₂ = 0; x₁ = 500.

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

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

Если координаты пробной точки обращают неравенство в истинное числовое неравенство, то полуплоскость, которой она принадлежит, является искомой. На рисунке 3.1 искомая полуплоскость выделена штриховкой.

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

Подобным образом следует поступить с каждым ограничением и граничным условием задачи ЛП (рис. 3.2).

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

Рис.3.2. ОДР по ограничениям задачи

 

Рис.3.3 Нахождение общей ОДР задачи

 

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

Выделенному многоугольнику (рис. 3.4) области допустимых решений соответствуют шесть опорных решений – шесть угловых точек: О (0; 0); А(0; 350); В (212, 5; 350); Д (312, 5; 300); Е (346, 15; 246, 15); F (100; 0).

Координаты точки Д (312, 5; 300 ) можно найти, вычислив координаты точки пересечения прямых по молоку и наполнителю, для чего нужно решить систему уравнений:

0, 8x₁ + 0, 5x₂ =400

0, 4x₁ + 0, 8x₂ =365

 

откуда x₁ = 312, 5; x₂ = 300.

 

Далее подставляем координаты каждой угловой точки в целевую функцию и определяем доход: А-4900; В-8300; Д-9200; Е-8984, 5; F-1600.

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

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

Рис.3.4 Нахождение оптимального решения

 

Этап 3-4. Для визуального выявления оптимального решения среди этих опорных решений используем следующие теоретические понятия.

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

Например, уравнение линии уровня 1600 будет иметь вид: 16x₁+14₂=1600 или уравнение линии уровня 4900 - 16x₁+14x₂=4900 (соответственно: прямая 1и 2, рис.3.5) и т.д.

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

Под градиентом целевой функции понимается вектор с началом в текущей точки плоскости x=(x_1, x₂), координаты которого рассчитываются, как значение частных производных целевой функции F (х) в этой точке:

grad F(x)= ,

Градиент целевой функции обладает двумя характерными свойствами:

1) Перпендикулярен линиям уровня целевой функции;

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

Например, нам необходимо найти новое значение коэффициента a¹₅₂ =14 на втором шаге (см.табл.).

 

Прямоугольник для него будет:

 

Также находим значения всех коэффициентов на втором шаге (см.табл.).

 

 

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

- выпускается 100 кг сливочного мороженого (x₁=100); шоколадное не выпускается (x₂=0);

- избыток наполнителя составляет 325 кг (x₄=325);

- спрос на сливочное мороженое удовлетворяется полностью (уравнение 3 системы 3.6 ( x₁-x₂=100; 100-0=100, т.е. x₅=0);

- избыток спроса на шоколадное мороженое составляет 350 кг (x₆=350);

- доход составляет 1600 руб.

Указанные числа записаны в столбце свободных членов на втором шаге симплекс-таблицы. Как видно, данные этого столбца свободных членов по-прежнему представляют собой параметры рассматриваемой задачи, хотя они и претерпели значительные изменения. Изменились и данные других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца переменной х_{2 .} Число ( -1) показывает, на сколько увеличится выпуск сливочного мороженого, если запланировать выпуск 1 кг. шоколадного мороженого. Число 30 в строке целевой функции показывает, что если будет запланирован выпуск шоколадного мороженого в количестве 1 кг., то это обеспечит увеличение дохода (значения целевой функции) на 30 руб.: 1600 +30=1630. Одновременно на 1 кг. вырастет выпуск сливочного мороженого, т.е. 16*101 + 14*1=1630 руб.

Числа 1, 3; 1, 2; 1 показывают соответственно, что при этом плане (х₁=101 и х₂=1) потребуется дополнительно увеличить расход молока на 1, 3 кг. , наполнителя – на 1, 2 кг. и на 1 кг. уменьшить лимит спроса на шоколадное мороженое:

320 – (400 – (0, 8*101 + 0, 5*1)) = 320 – 318, 7 = 1, 3

3 25 – (365 – (0.48101 + 0.8*1)) = 325 – 323.8 = 1, 2

350 – (350 – (1*1)) = 350 – 349 = 1

Несколько иное экономическое содержание имеют числа, записанные в столбце при переменной х_5. Число 1 во 3-й строке 2-го шага этого столбца показывает, что изменение разницы в спросе между сливочным и шоколадным мороженым на 1 кг. позволило бы увеличить выпуск сливочного мороженого на 1 кг.: ((100 + 1/1) – 100)) = 1. Одновременно, потребовалось бы дополнительно 0, 8 кг молока и 0, 4 кг наполнителя (т.е.

избыток этих ресурсов сократился бы соответственно до 320 – 0, 8 = 319, 8 кг.

и 325 – 0, 4 = 324, 6 кг.)

Увеличение выпуска сливочного мороженого на 1 кг. приведет к росту дохода на 16 руб (строка 5) – 16*(100 + 1) = 1616 руб.

 

Далее возвращаемся к этапу 3 и проверяем полученный план на оптимальность. Из строки целевой функции видно, что она содержит положительный коэффициент c ₅₂ = 30 (см.табл.), т.е. план не оптимальный и его можно улучшить путем введения в план выпуск шоколадного мороженого (x₂), так как любое значение x₂> 0 увеличивает значение целевой функции.

Выполняя последовательно этапа 3-5, получаем окончательную симплексную таблицу. В этой таблице все коэффициенты в строке целевой функции отрицательные или равные нулю, т.е. полученный план оптимален, т.е. нет ни одной переменной, введение которой в план увеличилось бы значение целевой функции в 9200 руб.

Оптимальное решение:

x₁=312, 5; x₂=300; x₃=x₄ =0; x₅= 87, 5 x₆ =312, 5; F(x)=9200.

Последовательность решения ЗЛП симплекс- методом

 

Оптимальное решение

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

При интерпретации результатов оптимизации в задаче об ассортименте продукции нас прежде всего интересуют объемы производства мороженого, т.е. значение управляемых переменных х₁ и х₂. Используя данные, содержащиеся в симплекс-таблице для оптимального решения, основные результаты можно представить в следующем виде:

Управляемые переменные	Оптимальные значения	Решение
х1 х2	312, 5	Объем производства сливочного мороженого должен быть равен 312, 5 кг. Объем производства шоколадного мороженого должен быть равен 300 кг.
Fmax		Доход от реализации мороженого должен рав-няться 9200 руб.

Статус ресурсов

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

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

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

Ресурс	Базисная (балансная) переменная	Статус ресурса
Молоко Сырье В Спрос Спрос	Х3=0 Х4=0 Х5=87, 5 Х6=50	Дефицитный Дефицитный Недефицитный Недефицитный

 

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

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

 

Ценность ресурса

Ценность ресурса характеризуется величиной улучшения оптимального значения F, приходящегося на единицу прироста объема данного ресурса. Графическая интерпретация этого определения применительно к условиям задачи об ассортименте продукции была дана в п. 3.2.1 (вторая задача на чувствительность). Графический анализ показывает, что ценность ресурсов соответственно равна:

u₁ =16, 36 д. е. на единицу прироста запаса молока; u₂=7, 27 д.е. на единицу прироста наполнителя; u₃ = 0= u₄ = 0;

Эта информация представлена в оптимальной таблице. Обратим внимание на значения коэффициентов в строке целевой функции (последняя итерация симплекс-таблицы). Значения указанных коэффициентов (16, 36; 7, 27; 0; 0) в точности соответствуют значениям, полученным при графическом решении.

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

 

 

Элементы модели

Искомые неизвестные	Целевая функция
u₁, u₂, u₃, u₄	Z(u)=400u₁ +365u₂ +100u₃ +350u₄
Ограничения
0, 8u₁ +0, 4u₂ +u₃ +0u ≥ 16 0, 5u₁ +0, 8u₂ -u₃ +u₄ ≥ 14 u₁, u₂, u₃, u₄ ≥ 0

 

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

Целевая функция исходной задачи формируется как сумма произведений строки переменных (количество продуктов разного типа x₁, x₂ ) на строку дохода от производства единицы каждого продукта; целевая функция двойственной задачи - как сумма произведений столбца переменных (теневых цен ресурсов u₁ -u₄ ) на столбец запасов этих ресурсов.

Аналогично ограничение на расход каждого из используемых ресурсов в исходной задаче формируется как сумма произведений строки переменных (x₁, x₂ ) на расход данного ресурса при производстве единицы каждого продукта. Ограничение на выручку от продажи ресурсов, идущих на производство данного продукта в двойственной задаче, формируется как сумма произведений столбца теневых цен (u₁ -u₄ ) на столбец расходов каждого из используемых ресурсов на производство единицы данного продукта.

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

 

Теорема двойственности

Пусть дана пара взаимодвойственных задач линейного программирования (3.7) и (3.8). Относительно этих задач имеет место следующая основная (первая) теорема двойственности.

Решение двойственной задачи

 

Составим и найдем решение двойственной задаче к задаче, решенной графическим и симплекс-методом.

Прямая задача:

Найти =(x₁, x₂ ), чтобы

F(x) =16x₁ +14x₂ → max, при

0, 8x₁ +0, 5x₂ ≤ 400

0, 4x₁ +0, 8x₂ ≤ 365

x₁ - x₂ ≤ 100

x₂ ≤ 350

x₁, x₂ ≥ 0

Решение прямой задачи:

x₁ =312, 5кг; x₂ =300кг

F(x) =9200 руб.

При этом первое и втрое ограничение превращается в строгое равенство, а третье и четвертое в строгое неравенство.

 

Двойственная задача:

Найти =(u₁, u₂, u₃, u₄ ), чтобы

Z (u) = 400u₁ +365u₂ +100u₃ +350u₄ → min

при 0, 8u₁ +0, 4u₂ +u₃ +0u₄ ≥ 16

0, 5u₁ +0, 8u₂ -u₃ +u₄ ≥ 14

u₁ - u₄ ≥ 0

 

Относительно рассматриваемого варианта задач соответствующие условия “дополняющей нежесткости” первой и второй группы выглядит следующим образом.

 

 

u₁ ↔ (400-0, 8x₁ -0, 5x₂ )=0;

u₂ ↔ (365-0, 4x₁ -0, 8x₂ )=0; (3.12)

u₃↔ (100 - x_{1 +} x₂)= 0;

u₄↔ (350 - x₂ ) =0.

 

x₁ ↔ (0, 8u₁ +0, 4u₂ + u₃ -16)=0; (3.13)

x₂ ↔ (0, 5u₁ +0, 8u₂ -u₃ +u₄ -14)=0;

Из группы условий (3.12), так как 100-312, 5+300=87, 5> 0 и 350-300=50> 0 и на основе интерпретации 1б следует, что ограничения по спросу не лимитируют оптимальную программу, т.е. u₃ =u₄ =0

Из группы условий (3.13) на основе интерпретации 2а следует, что если оба продукта выпускаются по оптимальной программе, т.е. x*₁ =312, 5 и x*₂ =300, то должны выполняться равенства

0, 8u₁ +0, 4u₂ +u₃ =16

0, 5u₁ +0, 8u₂ -u₃ +u₄ =14

Из этих уравнений с учетом u₃ =u₄ =0 перейдем к решению следующей системы

0, 8u₁ +0, 4u₂ =16

0, 5u₁ +0, 8u₂ =14

 

Откуда получаем u ₁ = (16, 36) руб. и u₂ = (7, 27) руб. , при этом

 

Z (u) =400 · +365· =9200 руб. т. е F (x) = Z (u) =9200 руб.

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

u₁ =16, 36 - величина ожидаемого прироста максимума дохода (9200 руб.) от дополнительного вовлечения в производство 1 кг молока к имеющимся 400кг;

u₂ =7, 27 руб.- величина ожидаемого прироста максимума дохода (9200 руб.) от дополнительного вовлечения в производство 1кг наполнителя к имеющимся 365 кг

u₃ =u₄ =0 руб. - величина ожидаемого прироста дохода за счет увеличения спроса (недефицитные) ресурсы.

В связи с этим «теневые цены» (u) в советской и российской литературе называются предельной эффективностью ресурса. Графическое решение двойственной задачи приведено на рис.3.13

 

40 A U2

35

30

25

20

15

10

7.27 B

5 U1

16.36

0 5 10 15 20 25 C30 35 40

Рис. 3.13 Графическое решение двойственной задачи

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

Из первой теоремы двойственности следует, что U = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис

.

 

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

 

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда U = C*A^-1 =

 

Оптимальный план двойственной задачи равен:

u₁ = 16.36

u₂ = 7.27

u₃ = 0

u₄ = 0

Z(U) = 400*16.36+365*7.27+100*0+365*0 = 9200

1, 818 312, 5

0, 909 50

Тогда max в₁≤ min

-55 ≤ △ в₁≤ 32, 1

Таким образом, ресурс «молоко» может быть уменьшен на 55 кг или увеличен на 32, 1 кг. Диапазон изменения равен [ 400-55; 400+32, 1]=[345; 432, 1]. Верхняя граница полностью совпадает с ранее найденной. Аналогично можно найти пределы изменения ресурса «наполнитель». Пределы изменения недефицитных ресурсов по спросу искать не имеет смысла, потому что нижняя их граница находится непосредственно из оптимальной симплекс-таблицы ( 87, 5 и 50 – соответственно), а верхняя равна бесконечности. Все расчеты можно свести в результирующую таблицу.

 

Наименование ресурса	Двойственная оценка	Величина ресурса	Нижняя граница	Верхняя граница
Молоко	16, 36			432, 1
Наполнитель	7, 27		335, 38	392, 5
Спрос			12, 5	_
Спрос				_

 

Здесь также можно определить целесообразность дополнительного приобретения дефицитного ресурса.. Например, определить, выгодно ли приобретать дополнительно молоко в количестве 20 кг. по цене с₁ = 15 руб. за 1 кг.

Увеличение запаса молока на величину ∆ b₁ = 20 кг. находится в пределах устойчивости двойственных оценок. Следовательно, ∆ F=u_{i *} ∆ b_i = 16, 36*20 =327, 2 руб. Затраты на приобретение 20 кг. молока составляют:

 

∆ с = ∆ b₁ * с₁ = 20 * 15 = 300 руб.

 

Поскольку величина дополнительных доходов (∆ F_max ) больше дополнительных затрат (327, 2> 300) закупать молоко в размере 20 кг. по цене с₁ = 15 руб. целесообразно.

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

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

Пусть предприятие нашло возможность увеличить запас молока на 10 кг.

Базисные переменные	Оптимальное решение	Коэффициенты структурных сдвигов (ас)	Произведение ac 10	Расчет варианта плана
X2 X5 X1 X6	87, 5 312, 5	-0, 9 -2, 727 1, 818 0, 909	-9 -27, 27 18, 18 9, 09	60, 23 330, 68 59, 09
F (X)		u1=16, 36	163, 6	9363, 6

В результате производство сливочного мороженого возросло, шоколадного - снизилось, спрос на сливочное и шоколадное мороженое тоже изменился.

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

Способа производства

 

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

Согласно третьему свойству двойственных оценок в оптимальный план включается нового продукция j-го вида, для которой выполняется условие

Оценим целесообразность введения в оптимальный план продукции третьего вида ( х₃ )-фруктового мороженого-, для которого технологические коэффициенты (нормы расхода): молоко – 0, 5; наполнителя - 0, 6, а доход – 12 руб.:

( 0, 5 * 16, 36 + 0, 6*7, 27) -12 =0, 542.

Так как доходы меньше затрат, то введение в план третьего вида продукции невыгодно.

 

Изменение ценовой политики предприятия.

 

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

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

 

 

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

 

Цена шоколадного мороженого может изменяться в пределах:

∆ c₂^- = min [u_k/a_2k] для a_2k> 0.

∆ c₂⁺ = |max [u_k/a_2k]| для a_2k< 0.

,

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

Таким образом, цена шоколадного мороженого может быть уменьшена на 4 или увеличена на 18 руб.

Интервал изменения равен:

(c₂ - ∆ c₂^-; c₂ + ∆ c₂⁺)

[14-4; 14+18] = [10; 32]

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

Цена сливочного мороженогои может изменяться в пределах:

∆ c₁^- = min [u_k/d_1k] для d_1k> 0.

∆ c₁⁺ = |max [u_k/d_1k]| для d_1k< 0.

 

Таким образом, может быть уменьшена на 9 или увеличен на 6.4 руб.

Интервал изменения равен:

(c₁ - ∆ c₁^-; c₁ + ∆ c₁⁺)

12345678910Следующая ⇒

Поделиться: