Методические основы ситуационного анализа

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

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

Методические основы ситуационного анализа

Постановка задачи

Для производства изделия двух типов А и В завод использует сырье четырех видов. При этом на изготовления единицы изделия вида А расходуется а₁ кг материала первого вида, а₂ кг материала второго вида, а₃ кг материала третьего вида и а₄ кг материала четвертого вида. На изготовление единицы изделия В расходуется b₁ кг материала первого вида, b₂ кг второго вида, b₃ кг третьего вида и, b₄ кг четвертого вида. На складе завода имеется всего материала первого вида с₁ кг, материала второго вида с₂ кг, материала третьего вида с₃ кг и материала четвертого вида с₄ кг. От реализации единицы готовой продукции типа А завода имеет прибыль б руб., а от продукции типа В прибыль составляет в руб.

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

Решение задачи

1. Составим математическую модель задачи. Данные задачи сведем в таблицу.

Продукция	A (x1)	A (x2)	Запасы сырья
Сырье
S1	a1 = 2	b1 = 3	c1 = 21
S2	a2 = 1	b2 = 0	c2 = 4
S3	a3 = 0	b3 = 1	c3 = 6
S4	a4 = 2	b4 = 1	c4 = 10
L	б = 3	в = 2

Обозначим через x₁ и x₂ количество выпускаемой продукции А и В. От реализации всей продукции А и В предприятие получает соответственно прибыль в размере б · x₁ и в · x₂, следовательно, целевая функция L имеет вид: L = б · x₁ + в · x₂, > max

Здесь: L = 3 · x₁ + 2 · x₂, > max

Расход материалов 1-го сорта (S₁) на производство всей продукции вида А и В составляет соответственно a₁ · x₁ и b₁ · x₂ единицы и не должен превышать запасов материалов данного сорта. Аналогично и по другим сортам материалов. При этом неизвестные x₁ и x₂ (количество выпускаемой продукции) должны удовлетворять условию: x₁ ? 0, x₂, ? 0.

Таким образом, получаем:

L = б · x₁ + в · x₂, > maxL = 3 · x₁ + 2 · x₂, > max

a₁ · x₁ + b₁ · x₂ ? c₁2 · x₁ + 3 · x₂ ? 21

a₂· x₁ + b₂ · x₂ ? c₂2 · x₁ + 0 · x₂ ? 4(1)

a₃ · x₁ + b₃ · x₂ ? c₃0 · x₁ + 1 · x₂ ? 6

a₄ · x₁ + b₄ · x₂ ? c₄2 · x₁ + 1 · x₂ ? 10

x₁ ? 0, x₂, ? 0x₁ ? 0, x₂, ? 0

ГРАФИЧЕСКИЙ СПОСОБ

Используя систему ограничений и условие не отрицательности, построим Область Допустимых Решений (ОДР). Для этого в системе (1) знаки неравенств заменим на знаки равенств.

В результате получим уравнения прямых, которые построим по точкам в системе координат Х₁ОХ₂. Так как у нас две переменные, то геометрически неравенства будут изображаться полуплоскостями, а их границы - прямыми линиями. При этом x₁ ? 0, x₂, ? 0, т.е. все решения будут располагаться в I-й четверти.

L₁:a₁ · x₁ + b₁ · x₂ = c₁2 · x₁ + 3 · x₂ = 21

x₁ = 0, x₂ = 7

x₂ = 1, x₁ = 9

L₂:a₂ · x₁ + b₂ · x₂ = c₂1 · x₁ + 0 · x₂ = 4

x₁ = 4

L₃:a₃ · x₁ + b₃ · x₂ = c₃0 · x₁ + 1 · x₂ = 6

x₂ = 6

L₄:a₄ · x₁ + b₄ · x₂ = c₄2 · x₁ + 1 · x₂ = 10

x₁ = 2, x₂ = 6

x₂ = 2, x₁ = 4

Прямые L₁, L₂, L₃, L₄ образуют многоугольник, который является границей множества планов. Линейная функция достигает своего минимального (максимального) значения в угловой точке (вершине) многогранника решений. Требуется найти максимум функции Z на многоугольнике допустимых планов.

Направление возрастания функции нескольких переменных ( в данном случае - двух) указывает вектор-градиент:grad Z, компонентами которого являются частные производные от функции Z по x₁ и x₂. Целевая функция:

Z = б · x₁ + в · x₂ = 3 · x₁ + 2 · x₂>

? Z / ? x₁ = б = 3

? Z / ? x₂ = в = 2

То есть, grad Z = {б ; в } = n = {3; 2}

Изобразим вектор n на графике. Строим прямую нулевого уровня функции Z:

Z = б · x₁ + в · x₂ =3 · x₁ + 2 · x₂, = 0

x₁ = 0, x₂ = 0

x₁ = 2, x₂ = - 3

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

Для нахождения оптимального плана будем «передвигать» линию нулевого уровня функции Z(x₁, x₂ ) параллельно самой себе в направлении, указанном вектором grad Z до точки ее «последней встречи» с многоугольником, которая и является оптимальным планом задачи. (То есть, при дальнейшем перемещении эта линия не будет иметь с ОДР общей точки). Здесь это точка М пересечения прямых L₁ и L_4:

L₁:a₁ · x₁ + b₁ · x₂ = c₁2 · x₁ + 3 · x₂ = 21

L₄:a₄ · x₁ + b₄ · x₂ = c₄2 · x₁ + 1 · x₂ = 10

Решая систему этих двух уравнений находим координаты точки М: М (2,25; 5,5).

Таким образом, максимальная прибыль:

Z _max = б · x^*₁ + в · x^*₂ = 2,25 · 3 + 5,5 · 2 = 17,75 (тыс. руб.)

То есть, если завод будет выпускать изделия типа А и В в количестве x^*₁ = 2,25 и x^*₂ = 5,5 изделий соответственно, то получит максимальную прибыль в размере

Z _max = 17,75 (тыс. руб.)

СИМПЛЕКС-МЕТОД

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

Условие оптимальности плана: ЗЛП на максимум, то в L - строке не должно быть отрицательных элементов, если ЗЛП на минимум, то в L - строке не должно быть положительных элементов.

1). Исходную ЗЛП приводим к каноническому виду путем введения базисных переменных. Для этого в системе (1) знаки неравенства заменяем на знаки равенства. При этом, если знак неравенства ?, то в левой части неравенства необходимо добавить неотрицательную переменную x_i, если знак ?, то в левой части неравенства необходимо вычесть некоторую неотрицательную величину x_{j .} В результате преобразований будем иметь:

L = б · x₁ + в · x₂, > maxL = 3 · x₁ + 2 · x₂, > max

a₁ · x₁ + b₁ · x₂ + x₃ = c₁2 · x₁ + 3 · x₂ + x₃ = 21

a₂ · x₁ + b₂ · x₂ + x₄ = c₂1 · x₁ + 0 · x₂ + x₄ = 4

a₃ · x₁ + b₃ · x₂ + x₅ = c₃0 · x₁ + 1 · x₂ + x₅ = 6

a₄ · x₁ + b₄ · x₂ + x₆ = c₄2 · x₁ + 1 · x₂ + x₆ = 10

x₁ ? 0, x₂, ? 0, x₃ ? 0, x₄, ? 0, x₅ ? 0, x₆ ? 0

Переменные x₁, x₂ будем считать свободными, а переменные x₃ , x₄, x₅ , x₆ - базисными.

2) Базисные переменные выражаем через свободные:

x₃ = 21 -2 · x₁ - 3 · x₂

x₄ = 4 - 1 · x₁ - 0 · x₂

x₅ = 6 - 0 · x₁ - 1 · x₂

x₆ = 10 - 2 · x₁ - 1 · x₂

3) Строим начальный план, полагая свободные переменные равными нулю, тогда базисные переменные будут равны свободным членам: X₀ = (0; 0; 21; 4; 6;10)

4) Строим первую симплекс-таблицу

Св. пер.	- x 1	- x 2	Свободные члены (c I )	Симплексные отношения
Баз. пер.
x 3	2	3	21	10,5
x 4	1	0	4	4 = min
x 5	0	1	6
x 6	2	1	10	5
L - строка	-3 Max (min)	- 2

5). Проверяем план на оптимальность. Задача на максимум, т.е. если в L - строке есть отрицательные члены, то план не оптимален. Улучшаем план.

6. Улучшение плана. Строим вторую симплекс-таблицу, элементы которой пересчитываем по соответствующим формулам.

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

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

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

{Пункты а) - в) мы выполняем для того, чтобы определить переменную, подлежащую исключению из базиса}.

Из базиса новой симплекс-таблицы выводим переменную x₄ и вводим переменную x₁ (это так для данного случая!).

г) Новая таблица:

· элемент ведущей ячейки делим на ведущий элемент;

· элементы ведущей строки делим на ведущий элемент; К КАЖДОЙ ИЗ ОСТАЛЬНЫХ СТРОК ПРИБАВЛЯЕМ ВНОВЬ ПОЛУЧЕННУЮ, УМНОЖЕННУЮ НА ТАКОЕ ЧИСЛО, ЧТОБЫ В КЛЕТКАХ ДЛЯ ВЕДУЩЕГО СТОЛБЦА ПРЕДЫДУЩЕЙ СИМПЛЕКС-ТАБЛИЦЫ ПОЯВИЛИСЬ НУЛИ, И ПИШЕМ ПРЕОБРАЗОВАННЫЕ СТРОКИ НА МЕСТО ПРЕЖНИХ ! или делаем как ниже:

· элементы ведущего столбца делим на ведущий элемент, умноженный на (-1);

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

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

Св. пер.	- x 4	- x 2	Свободные члены (c I )	Симплексные отношения
Баз. пер.
x 3	0	3	13	13/3
x 1	1	0	4
x 5	0	1	6	6
x 6	0	1	2	2=min
L - строка	0	-2 Max (min)	12

7) Вновь полученный план проверяем на оптимальность.

План, соответствующей последней таблице: X _k = (4; 0; 13/3; 0; 6; 0)

План НЕ оптимален, т.к. в L - строке есть отрицательный член. Улучшаем план. Строим новую симплекс-таблицу:

Св. пер.	- x 4	- x 6	Свободные члены (c I )	Симплексные отношения
Баз. пер.
x 3	0	0	7
x 1	1	0	2,25
x 5	0	0	4
x 2	0	1	5,5
L - строка	0	0	17,75

План, соответствующей последней таблице: X _k = (4; 2; 0; 0; 0; 0)

План оптимален, т.к. в L - строке нет отрицательных членов

Ответ: если предприятие будет выпускать изделия типа А и В в количестве

X^*₁ = 2,25 и X^*₂ = 5,5 единиц соответственно то получит максимальную прибыль в размере L _max = 2,25 · 4 + 5,5 · 2 = 17,75 (тыс. руб.)

2. Решение задачи с помощью пакета MS Excel и надстройки «Поиск решения»

Теоретической основой надстройки Поиск решения является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающим планам. «Поиск решения» является дополнением MS Excel, т.е. может не входить в стандартный вариант установки электронных таблиц. Для его добавления достаточно воспользоваться командой СЕРВИС > Надстройки > Поиск решения. После заполнения формы на свободном листе Excel, вызывается опция Поиск решения, в диалоговом окне которого выполняются необходимые настройки.

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

Переменные				Целевая функция:	L= a*x1 + b*x2
x1	x2
2,25	5,5			a	b
Функция цели		17,75		3	2

ВЫВОД

Все три метода (Графический, Симплекс-метод, Поиск решения с помощью MS Excel) показали:если предприятие будет выпускать изделия типа А и В в количестве

X^*₁ = 2,25 и X^*₂ = 5,5 единиц соответственно, то получит максимальную прибыль в размере

L _max = 2,25 · 4 + 5,5 · 2 = 17,75 (тыс. руб.)

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

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

2. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции?

3. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции?

Так как величина запасов каждого из ресурсов фиксируется в правых частях ограничений, то этот вид анализа идентифицируется кака АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ К ПРАВОЙ ЧАСТИ ОГРАНИЧЕНИЙ.

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

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

предельно допустимое увеличение запасов дефицитного ресурса, позволяющее улучшить найденное оптимальное решение;

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

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

L₁:2 · x₁ + 3 · x₂ ? 21точка М (x^*₁ = 2,25 и x^*₂ = 5,5)

L₂:1 · x₁ + 0 · x₂ ? 4

L₃: 0 · x₁ + 1 · x₂ ? 6

L₄:2 · x₁ + 1 · x₂ ? 10

Имеем:

L₁ (М): 2 · 2,25 + 3 · 5,5 = 4,5 + 16,5 = 21 ? 21- используется полностью

L₂ (М):1 · 2,25 + 0 · 5,5 = 1,25 ? 4- избыток сырья с₂ = 4 - 1,25 = 2,75

L₃ (М): 0 · 2,25 + 1 · 5,5 = 5,5 ? 6- избыток сырья с₃ = 6 - 5,5 = 0,5

L₄ (M):2 · 2,25 + 1 · 5,5 = 10 ? 10- используется полностью

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

ИЗБЫТОЧНЫМИ называются ограничения, которые в данной ситуации даже напрямую не участвуют в формировании пространства допустимых решений.

Из графика к данной задаче мы видим, что избыточных запасов в данном случае нет, так как все четыре ограничения участвуют в формировании ОДР.

 Если цена изделия В возрастет до 3 тыс. руб., как это повлияет на выбор решения?

Воспользуемся пакетом MS EXCEL и надстройкой «Поиск решения»

Переменные				Целевая функция:	L= a*x1 + b*x2
x1	x2
				a	b
Функция цели		0		3	3
Ограничения				Ограничения:	a1*x1 + b1*x2 <= c1; a2*x1 + b2*x2 <= c2
0	21
0	4			a1	a2	a3	a4
0	6			2	1	0	2
0	10

Табл

Переменные				Целевая функция:	L= a*x1 + b*x2
x1	x2
2,25	5,5			a	b
Функция цели		17,75		3	2
Переменные				Целевая функция:	L= a*x1 + b*x2
x1	x2
2,25	5,5			a	b
Функция цели		23,25		3	3

производство сбыт excel

ВЫВОД: При увеличении цены изделия В до 3 тыс. руб. целевая функция Z _max возрастает с 17,5 до 23,25 тыс. руб. при условии, что завод будет выпускать изделия типа А и В в количестве x^*₁ = 2,25 и x^*₂ = 5,5 изделий соответственно, как и при цене изделия В 2 тыс. руб.

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

...