Оптимизация ассортимента продукции

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

Задание № 1

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

Таблица 1 - Исходные данные

Вид проката	Масса металла для производства тонны продукции, тонн	Доход от производства, тыс. руб.	Брак %	Энергозатраты, тыс. руб.
Проволока	1,18	5	0,2	7
Лента	1,1	3	0,1	3

В день со склада может поступать и не более 15 тонн металла для производства проволоки и ленты. Количество брака за сутки не должно превышать 0,19 тонн металла. Энергозатраты не должны превышать по договору с электростанцией 150 тыс. руб.

Решение.

Пусть х₁, х₂ - количество (тонн) проволоки и ленты соответственно, планируемое к выпуску. Тогда суммарная прибыль от реализации всей плановой продукции (целевая функция) составит z = 5•х₁ + 3•х₂ > max. При этом общий расход металла равен 1,18•х₁ + +1,1•х₂, и он не должен превышать 15 тонн. Это приводит к ограничению 1,18•х₁ + 1,1•х₂?15. Аналогично учитываются ограничения по браку и энергозатратам: 0,2•х₁ + 0,1•х₂?0,19, 7•х₁ + +3•х₂?150. Так как объемы выпускаемых изделий не могут быть отрицательны, то х₁?0, х₂ ?0.

Таким образом, математическая модель задачи имеет вид:

z = 5•х₁ + 3•х₂ > max (1)

1,18•х₁ + 1,1•х₂?15 (2)

0,2•х₁ + 0,1•х₂?0,19 (3)

7•х₁ + 3•х₂?150 (4)

х₁?0, х₂ ?0 (5)

Таким образом, задача состоит в том, чтобы найти неотрицательные значения x_i (i=1,2), удовлетворяющие ограничениям (2)-(4), для которых z принимает наибольшее значение.

Построим область допустимых решений (рис. 1), т.е. решим графически систему неравенств. Для этого построим каждую прямую (ограничения 2 - 4) и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Условия (5) ограничивают ОДР первой четвертью.

Рисунок 1 - Область допустимых решений

Обозначим границы области многоугольника решений (рис.2).

Рисунок 2 - Границы многоугольника решений

Рассмотрим целевую функцию задачи z = 5•х₁ + 3•х₂ > max.

Построим прямую (линию уровня), отвечающую значению функции z = 0:

z = 5•х₁ + 3•х₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую вдоль вектора с = (5, 3) до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией (рис.3).

Рисунок 3 - Нанесение линий уровня

Прямая z = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (2) и (5), то ее координаты удовлетворяют уравнениям этих прямых: 0,2x₁+0,1x₂=0,19 и x₁=0.

Решив систему уравнений, получим: x₁ = 0 (т.), x₂ = 1,9 (т.).

Откуда найдем максимальное значение целевой функции: z = 5•0 + 3•1,9 = 5,7 тыс.руб.

Проведем анализ чувствительности оптимального решения (анализ сокращения или увеличения ресурсов) для следующих задач:

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

b. на сколько можно уменьшить запас недефицитного ресурса при сохранении оптимального значения ЦФ?

c. увеличение запаса какого из ресурсов наиболее выгодно?

Анализ моделей на чувствительность проводится после получения оптимального решения задачи. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели.

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

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

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

На сколько можно сократить или увеличить объемы выпускаемой продукции?

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

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

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

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

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

1. предельно допустимое увеличение объема дефицитного изделия (лента), позволяющее улучшить найденное оптимальное решение

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

Результаты проведенного анализа можно свести к следующему:

a. на сколько можно увеличить запас дефицитного ресурса для улучшения оптимального значения ЦФ? - дефицитного ресурса нет

b. на сколько можно уменьшить запас недефицитного ресурса при сохранении оптимального значения ЦФ? - для сохранения оптимального значения ЦФ не нужно уменьшать запасы недефицитного ресурса.

c. увеличение запаса какого из ресурсов наиболее выгодно? - увеличение запаса 1 ресурса более выгодно

Задание № 2

прибыль гаусс симплекс уравнение

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

Таблица 2 - Исходные данные

Тип оборудования	Затраты времени (станко/ч) на единицу продукции вида	Общий фонд рабочего времени (станко/ч)
	1	2	3	4
Токарное Фрезерное Шлифовальное	2 1 1	1 2	1 2 1	3 1	300 70 340
Прибыль от реализации единицы продукции (руб.)	8	3	2	1

Решение.

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

Определим максимальное значение целевой функции z = 8x₁+3x₂+2x₃+x₄ при следующих условиях ограничений:

2x₁+x₂+x₃+3x₄?300

x₁+2x₃+x₄?70

x₁+2x₂+x₃?340

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве вводим базисную переменную x₅. В 2-м неравенстве вводим базисную переменную x₆. В 3-м неравенстве вводим базисную переменную x₇.

2x₁ + 1x₂ + 1x₃ + 3x₄ + 1x₅ + 0x₆ + 0x₇ = 300

1x₁ + 0x₂ + 2x₃ + 1x₄ + 0x₅ + 1x₆ + 0x₇ = 70

1x₁ + 2x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ = 340

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид (табл.3):

Таблица 3 - Матрица коэффициентов

2	1	1	3	1	0	0
1	0	2	1	0	1	0
1	2	1	0	0	0	1

Решим систему уравнений относительно базисных переменных x₅, x₆, x₇, полагая, что свободные переменные равны 0, получим первый опорный план (табл. 4):

X1 = (0,0,0,0,300,70,340)

Таблица 4 - Первый опорный план

Базис	В	x1	x2	x3	x4	x5	x6	x7
x5	300	2	1	1	3	1	0	0
x6	70	1	0	2	1	0	1	0
x7	340	1	2	1	0	0	0	1
z	0	-8	-3	-2	-1	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке z выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

.

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 5 - Итерация 0.

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x5	300	2	1	1	3	1	0	0	150
x6	70	1	0	2	1	0	1	0	70
x7	340	1	2	1	0	0	0	1	340
z	0	-8	-3	-2	-1	0	0	0	0

После преобразований получаем новую таблицу 6:

Таблица 6 - Результат преобразований.

Базис	В	x1	x2	x3	x4	x5	x6	x7
x5	160	0	1	-3	1	1	-2	0
x1	70	1	0	2	1	0	1	0
x7	270	0	2	-1	-1	0	-1	1
z	560	0	-3	14	7	0	8	0

Итерация №1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке z выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

.

Следовательно, 3-ая строка является ведущей.

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

Таблица 7 - Итерация 1

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x5	160	0	1	-3	1	1	-2	0	160
x1	70	1	0	2	1	0	1	0	0
x7	270	0	2	-1	-1	0	-1	1	135
z	560	0	-3	14	7	0	8	0	0

После преобразований получаем новую таблицу 8:

Таблица 8 - Результат преобразований итерации 1

Базис	В	x1	x2	x3	x4	x5	x6	x7
x5	25	0	0	-2.5	1.5	1	-1.5	-0.5
x1	70	1	0	2	1	0	1	0
x2	135	0	1	-0.5	-0.5	0	-0.5	0.5
z	965	0	0	12.5	5.5	0	6.5	1.5

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план.

Окончательный вариант симплекс-таблицы (таблица 9):

Таблица 9 - Оптимальное решение

Базис	В	x1	x2	x3	x4	x5	x6	x7
x5	25	0	0	-2.5	1.5	1	-1.5	-0.5
x1	70	1	0	2	1	0	1	0
x2	135	0	1	-0.5	-0.5	0	-0.5	0.5
z	965	0	0	12.5	5.5	0	6.5	1.5

Ответ. Оптимальный план можно записать так:

x₅ = 25

x₁ = 70

x₂ = 135

z = 8*70 + 3*135 = 965.

Задание № 3

Таблица 10 - Матрица антагонистической игры:

	Игрок В (проигрыши)
Игрок А (выигрыши)	14	11	6	8
	4	5	5	4
	18	12	7	4

Решение.

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

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I (таблица 11).

Таблица 11 - Решение в чистых стратегиях

Игроки	B1	B2	B3	B4	a = min(Ai)
A1	14	11	6	8	6
A2	4	5	5	4	4
A3	18	12	7	4	4
b = max(Bi )	18	12	7	8	0

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 6, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min(b_j) = 7.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 6 ? y ? 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ? a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ? a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

Стратегия A1 доминирует над стратегией A2 (все элемент строки 1 больше или равны значениям 2-ой строки), следовательно, исключаем 2-ую строку матрицы (таблица 12).

Таблица 12 - Результат рассмотрения доминирования игрока А

14	11	6	8
18	12	7	4

С позиции проигрышей игрока В стратегия B1 доминирует над стратегией B2 (все элементы столбца 1 больше элементов столбца 2), следовательно исключаем 1-ой столбец матрицы.

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

Таблица 12 - Результат рассмотрения доминирования игрока В

6	8
7	4

В платежной матрице отсуствуют доминирующие строки.

В платежной матрице отсуствуют доминирующие столбцы.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

3. Находим решение игры в смешанных стратегиях.

Запишем систему уравнений.

Для игрока I

6p₁+7p₂ = y

8p₁+4p₂ = y

p₁+p₂ = 1

Для игрока II

6q₁+8q₂ = y

7q₁+4q₂ = y

q₁+q₂ = 1

Решая эти системы методом Гаусса, находим:

y = 6²/₅

p₁ = ³/₅ (вероятность применения 1-ой стратегии).

p₂ = ²/₅ (вероятность применения 2-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (³/₅; ²/₅)

q₁ = ⁴/₅ (вероятность применения 1-ой стратегии).

q₂ = ¹/₅ (вероятность применения 2-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (⁴/₅; ¹/₅)

Цена игры

y = 6²/_5.

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A₁, правый - стратегии A₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. На левой оси ординат откладываются выигрыши стратегии A₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A₂.

Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B₁B₁ и B₂B₂ (рис.4), для которых можно записать следующую систему уравнений:

y = 6 + (7 - 6)p₂

y = 8 + (4 - 8)p₂

Откуда

p₁ = ³/₅

p₂ = ²/₅

Цена игры, y = 6²/₅

Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений:

6q₁+8q₂ = y

7q₁+4q₂ = y

q₁+q₂ = 1

или

6q₁+8q₂ = 6²/₅

7q₁+4q₂ = 6²/₅

q₁+q₂ = 1

Решая эту систему методом Гаусса, находим:

q₁ = ⁴/₅

q₂ = ¹/₅

Рисунок 4 - Графическое представление решения

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