Методы оптимальных решений (стр. 5 )

B A	B1	B2	B3	Запасы
A1	2		3		1
	30		10		20	60
A2	4		2		5
			30			30
Потребности	30	40	20

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

Определим платежи и , решив систему уравнений.

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

Согласно теореме об оптимальности решения и, следовательно, исходное решение не является оптимальным, и его можно улучшить путем переноса перевозки x23 = 20 по циклу, построенному для клетки (1,3). В результате получили новое допустимое решение, соответствующее табл. 15. Проверим это решение на оптимальность.

Если , то , , , . Тогда Согласно теореме об оптимальности для всех свободных клеток и , и, следовательно, решение в табл. 15 является оптимальным.

9. подробные ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача на оптимизацию плана производства продукции графическим и симплекс – методом

Предприятие производит два типа кондитерских изделий А и В, в их состав входят какао, сахар и мука. На изделие А необходимо потратить 1 кг какао и 2 кг сахара, муки не нужно. На изделие В необходимо 3 кг какао, 1 кг сахара и 1 кг муки. Запасы какао 18 кг, сахара 16 кг, муки 5 кг. Цена изделия А 2 у. е., изделия В 3 у. е. Найти оптимальный план производства товаров А и В с максимальной прибылью.

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

Сырье	Производимый продукт	Запасы
А	В
Какао	1	3	18
Сахар	2	1	16
Мука	0	1	5
Цена	2	3

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

Обозначим неизвестное количество продукта А за х1, неизвестное количество продукта В за х2. Очевидно, что они неотрицательные. Поскольку количество не может быть меньше 0. Это позволит нам сформировать математическую модель производственного процесса.

Цена товара А равна 2 у. е. за единицу, значит общая прибыль от продажи товара А это его количество, умноженное на цену единицы: 2 * х1.

Аналогично с товаром В. Цена единицы товара 3 у. е. значит прибыль ищем как цену умноженную на общее, пока неизвестное, количество товара В: 3 * х2.

Прибыль от производства двух товаров – это сумма прибыли от производства каждого: 2х1 + 3х2. Нам необходимо найти такие значения x1 и x2, которые бы давали максимум данной суммы. При этом необходимо учитывать ограничения на ресурсы.

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

Ее чаще всего обозначают F = 2х1 + 3х2 → max, что означает поиск ее максимума.

Теперь необходимо сформировать ограничения на ресурсы. На один продукт А по условию задачи тратим 1 кг какао, на один продукт В мы его тратим 3 кг, всего какао на складе 18 кг. Значит если мы умножим затраты какао на количество каждого продукта, мы получим сколько всего тратиться какао. И эта сумма не должна превышать 18 кг. Таким образом ограничение по какао будет выглядеть:

1 * х1 + 3 * х2 ≤ 18

Аналогично записываем ограничения по сахару и муке.

По сахару: 2 * х1 + 1 * х2 ≤ 16,

По муке: 0 * x1 + 1* x2 ≤ 5.

Таким образом окончательно получаем математическую запись производственной задачи. Найти максимум функции F = 2х1 + 3х2 → max при наличии системы ограничений:

х1 + 3 х2 ≤ 18

2 х1 + х2 ≤ 16

x2 ≤ 5

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

Первый способ решения – графический.

Используется для решения задач, связанных с производством двух видов продуктов. Рисуем систему координат - оси, на которых мы будем откладывать количество продукта А и В. Берем только положительную зону, поскольку количество продуктов всегда неотрицательно. Ограничения на ресурсы переписываем со знаком равно и рисуем соответствующие прямые на системе координат.

Первое ограничение записываем как: х1 + 3 х2 = 18.

Строим эту прямую, задав два произвольных значения х1. Например: х1 = 6, тогда подставляем в уравнение: 6+3х2=18, значит х2=4. Ставим точку (6;4). Вторая точка например х1 = 3, тогда х2 = 5. Ставим точку. Соединяем эти точки. Это и есть прямая: х1 + 3 х2 = 18.

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

Берем второе неравенство и переделываем в уравнение: 2 х1 + х2 = 16. Аналогично строим две произвольных точки и проводим прямую. Возьмем, например, х1 =5, тогда из уравнения получим х2=6. Ставим точку. Вторую точку, например х1 = 7, тогда из уравнения получим х2 = 2. Рисуем точки и соединяем их прямой.

х2 2 х1 + х2 = 16

 

6

х2=5

5

 

4 х1 + 3 х2 = 18

2

х1

Рисунок 1 – Построения ограничений

Аналогично область решений лежит ниже прямой, поскольку в первоначальном ограничении стоит меньше или равно. Третье ограничение x2=5, это прямая параллельная оси х1, рисуем ее. Аналогично, область допустимых решений лежит на самой и ниже прямой. Все построения на рисунке 1. Теперь надо выделить ту область, где выполняются все три ограничения, т. е. где штриховки пересекаются.

х2 4 5

направляющая

3 х2=5

2 5 х1 + 3 х2 = 18

 

1 . оптимум

2 х1 + х2 = 16

3

2 3 6

0 х1

Рисунок 2 – Выделенная область решений и нахождение оптимального решения х1

Теперь рассмотрим нашу целевую функцию F = 2х1 + 3х2 → max

Берем коэффициенты этой функции и ставим на рисунке точку, соответствующую им. То есть точку (2;3). Строим прямую проходящую через (0,0) и эту точку (2,3). Такая прямая называется направляющей, на рисунке она выделена пунктиром.

Затем строим прямую из целевой функции 2х1 + 3х2 = с, где с – любое число. Она всегда будет перпендикулярна направляющей прямой. Мысленно двигаем ее по направляющей прямой в сторону границы нашей области, на рисунке движение показано тонкими линиями с номерами 1, 2, 3 ,4 и 5.

Пока часть прямой лежит в допустимой области – продолжаем двигать, до тех пор, пока не останется единственной точки соприкосновения. На рисунке видно, что в варианте 5 почти вся прямая вышла за область решений, осталась только одна тока соприкосновения. Это и есть максимальное из допустимых значений в данной области для нашей задачи. Мы видим, что это точка пересечения прямых: х1 + 3 х2 = 18 и 2 х1 + х2 = 16. Найдем их пересечение. Из первого уравнения выражаем х1 = 18 – 3 х2, подставляем во второе: 2 (18 – 3 х2) + х2 = 16, значит х2 = 4. Подставляем в первое: х1 =*4 = 6.

Таким образом, искомый план производства: продукт А – 6 шт., продукт В – 4 шт. Прибыль: F = 2*6+3*4 = 12+12 = 24 у. е. Решение найдено.

Второй способ решения – симплекс метод

Итак, мы сформулировали задачу

Найти максимум функции F = 2х1 + 3х2 → max при наличии системы ограничений:

х1 + 3 х2 ≤ 18

2 х1 + х2 ≤ 16

x2 ≤ 5

До этого момента все шаги одинаковые.

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

х1 + 3 х2 + х3 =

2 х1 + х2 + х4 =

x2 + х5 = 5 (3)

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

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

Первое уравнение: свободный член равен 18, коэффициент при х2 равен 3, их отношение равно 6.

Второе уравнение: свободный член равен 16, коэффициент при х2 равен 1, их отношение равно 16.

Третье уравнение: свободный член равен 5, коэффициент при х2 равен 1, их отношение равно 5.

Разрешающим выбираем уравнение, в котором отношение минимальное. В нашем случае это третье уравнение. Его мы оставляем без изменений. x2 + х5 = 5 (3*)

Из него выражаем х2.

х2 = 5 – х5

Подставляем это выражение вместо х2 в первое и второе уравнения.

Первое: х1 + 3 (5 – х5) + х3 = 18, открываем скобки и преобразуем:

х1 + х3 – 3 х5 = 3 (1*)

Подставляем во второе уравнение:

2х1 + (5 – х5) + х4 = 16, преобразуем 2 х1 + х4 –х5 = 11 (2*)

Теперь подставляем в целевую функцию: F = 2х1 + 3 (5 – х5) = 2 х1 – 3 х5 + 15.

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

х1 + х3 – 3 х5 = 3 (1*)

2 х1 + х4 –х5 = 11 (2*)

x2 + х5 = 5 (3*)

Функция: F* = 2 х1 – 3 х5 + 15.

Далее повторяем все действия. Снова смотрим при какой переменной в целевой функции максимальный положительный коэффициент.

Выбираем переменную х1 при ней максимальный положительный коэффициент 2.

Снова ищем отношения свободных членов уже преобразованных уравнений (1*) – (3*) к коэффициентам при переменной х1.

В (3*) нет х1, в (1*) отношение равно 3 (3 к 1), в (2*) отношение равно 5,5 (11 к 2). Выбираем минимальное отношение – это в уравнении (1*). Теперь оно будет разрешающим. Его оставляем без изменений х1 + х3 – 3 х5 = 3 (1**)

Выражаем из (1**) переменную х1: х1 = - х3 + 3 х5 + 3 , подставляем в (2*) и (3*).

В (3*) нет х1, оно не изменится: x2 + х5 = 5 (3**)

Из уравнения (2*) получаем: 2( - х3 + 3 х5 + 3) + х4 – х5 = 11, преобразуем его, открыв скобки: -2х3 + 5х5 + х4 = 5 (2**).

Подставляем х1 в целевую функцию

F ** = 2 х1 – 3 х5 + 15 = 2(- х3 + 3 х5 +х5 + 15= -2x3 + 3x5 +21

Новая система после преобразований:

х1 + х3 - 3 х5 = 3 (1**)

-2х3 + 5х5 + х4 = 5 (2**).

х2 + х5 = 5 (3**)

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

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

В первом уравнении свободный член 3 и коэффициент (-3), отношение равно -1, отрицательное, его не рассматриваем.

Во втором уравнении 5 свободный член и 5 коэффициент при х5, значит отношение равно 1.

В третьем уравнении отношение равно 5 (5 свободный член и 1 коэффициент).

Выбираем из них минимальное. Это в уравнении (2**). Оставляем его без изменений -2х3 + 5х5 + х4 = 5 (2***). Из него будем выражать переменную х5.

х5 = 1 + 2/5 х3 – 1/5 х4

Подставляем в (1**) и (3**) уравнения:

(1**): х1 +х3 – 3 (1 + 2/5 х3 – 1/5 х4) = 3

Преобразуем: х1 – 1/5 х3 + 3/5 х4 =6 (1***)

(3**) х2 + (1 + 2/5 х3 – 1/5 х4) = 5

Преобразуем: х2 + 2/5 х3 – 1/5 х4= 4 (3***)

Подставляем в целевую функцию: F*** = -2x3 + 3x5 +21 = -2х3 + 3 (1 + 2/5 х3 – 1/5 х4) +21 = -4/5 х3 -3/5х4 +24.

В целевой функции больше нет положительных коэффициентов. Решение закончено.

Для получения значений плана и прибыли приравниваем к 0 все переменные, которые остались в целевой функции F***, т. е. принимаем х3 и х4 равными 0.

Тогда F = 24 у. е. – это и есть максимальная прибыль от производства.

Аналогично подставляем х3 = х4 = 0 в последние полученные уравнения ограничений (1***) - (3***). Получим из (1***) х1 = 6 – это оптимальное количество продукта А.

Из (2***) х5 = 1, это мнимая переменная, ее ненулевое значение говорит о том, что у муки, к ограничению которой мы добавили эту переменную, будет остаток.

Из (3***) х2 = 4 – это оптимальное количество товара В.

Задача решена. Результат совпал с графическим методом решения.

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

Завод изготавливает два типа изделий А и В. На изделие А тратят 6 кг стали первого типа, 2 кг стали второго типа, и 2 кг стали третьего типа. Для производства изделия В используют 2 кг стали первого типа, 4 кг стали второго типа, сталь третьего типа не используется. Запасы стали первого типа 36 кг, стали второго типа 32 кг, стали третьего типа 10 кг. Цена изделия А = 6 у. е., цена изделия В = 4 у. е. Найти оптимальный план производства с максимумом п прибыли двумя методами: графическим и симплекс-методом

Оптимизация плана производства с 3-мя продуктами

Симплекс-метод

Задача. Для производства детали типа А необходимо затратить 1 кг стали перового типа, 3 кг стали второго типа, 1 кг стали третьего типа. Для производства детали типа В необходимо 2 кг стали первого типа и 4 кг стали третьего типа, для производства детали С 1 кг стали первого типа и 2 кг второго типа. Запасы стали 430 кг первого типа. 460 кг стали второго типа и 420 кг стали третьего типа. Определить оптимальный план производства с учетом ограничений на ресурсы и с максимальной прибылью от продажи деталей, если цена детали А = 3 з. е., детали В = 2 з. е., детали С = 5 з. е.

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

Деталь Тип стали	A	B	C	Запас стали
Первый	1	2	1	430
Второй	3	0	2	460
Третий	1	4	0	420
Цена	3	2	5

Из этой таблицы формулируем математическую модель экономической задачи. Для этого обозначим искомые, но неизвестные пока количества производимых деталей как a, b и с соответственно. Цена детали A = 3 у. е. за единицу, значит общий доход от ее продажи составит 3*a. Аналогично с деталями B и C. Доход их продажи 2*b и 5*с. Общий доход D = 3a + 2b + 5c. По условию задачи надо найти такие a,b, c, которые обращали бы функцию D в максимум, т. е.