Методы оптимизации производства

Содержание

 

Задача 1(13). ….……………………………………………………………..……3

Задача 2(63).………………………………………………………………..……5

Задача 3(113)………………………………………………………………..…..…8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача №1(13)

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

                          

Решение

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

                        

 Построим вектор и прямую , перпендикулярную , на плоскости Ox₁x₂. Перемещая прямую в направлении вектора - , получаем, что min значение z находится в точке A. Координаты этой точки определяются решением системы двух линейных уравнений (I) и (II), на пересечении которых она находится. В результате решения системы уравнений (I) и (II) получим оптимальное решение :

              

.

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

Введем двойственные переменные ; тогда двойственная задача будет иметь вид:

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2(63)

На предприятии имеется  несколько производственных линий.  j-я линия производит в единицу времени единиц продукции i-го типа. Для выполнения задания предприятию необходимо выпускать не менее единиц i-го типа продукции, при этом эксплуатационные расходы j-ой линии составляют млн. рублей в единицу времени. Определить время работы каждой линии для выполнения задания при условии минимизации затрат.

Решение:

Математическая модель исходной задачи:

x_j–время работы j-ой линии (в часах).

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

Построим симплекс-таблицу:

 

 

 

Б	x1	x2	x3	x4	y1	y2	- z,β	Θ
z	10	12	8	10	0	0	0
y1	-2	-1	-3	-1	1	0	-18	18
y2	-1	-1	-4	-4	0	1	-20	5
z	7   1/2	9  1/2	-2	0	0	2   1/2	-50
y1	-1   3/4	-   3/4	-2	0	1	-   1/4	-13	6   1/2
x4	1/4	1/4	1	1	0	-   1/4	5	5
z	8	10	0	2	0	2	-40
y1	-1   1/4	-   1/4	0	2	1	-   3/4	-3	2   2/5
x3	1/4	1/4	1	1	0	-   1/4	5	20
z	0	8   2/5	0	14   4/5	6   2/5	-2   4/5	-59   1/5
x1	1	1/5	0	-1   3/5	-   4/5	3/5	2   2/5
x3	0	1/5	1	1   2/5	1/5	-   2/5	4   2/5
z	4   2/3	9   1/3	0	7   1/3	2   2/3	0	- 48
y2	1   2/3	1/3	0	-2   2/3	-1   1/3	1	4
x3	2/3	1/3	1	1/3	-   1/3	0	6

 

Заметим, что все β>0 и все приведенные стоимости (коэффициенты при x_j в строке z) также неотрицательны. Это значит, что полученный план является оптимальным:

, z*=

Сформулируем двойственную задачу.

 Целевая функция примет вид:

Ограничения:

Экономическая интерпретация двойственной задачи.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3(113)

Завод имеет 4 цеха A, B, C, D и 5 складов. Производительность i-го цеха за смену составляет П_i тыс. шт. деталей, ; пропускная способность j-го склада за это время составляет Е_j тыс. шт. деталей, . Стоимости перевозок 1 тыс. шт. деталей из цеха i в склад j задаются матрицей . Составить такой план перевозки изделий, при котором расходы на перевозку изделий были бы наименьшими.

	Еj
	37	26	91	24	13
20	14	13	6	12	1
30	18	20	4	2	3
70	17	5	15	10	8
71	4	12	18	13	16

 

Решение:

Постановка транспортной задачи  в общем виде:

      

количество единиц изделий, которое  нужно доставить из i-ПО в j-ПН

Подставим исходные данные:

 транспортная задача является  закрытой.

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

Нахождение оптимального плана перевозок:

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

Решим систему уравнений  , которые соответствуют базисным клеткам,

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

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

Выбираем свободную  клетку (3,4), присваиваем ей знак «+» и переносим по этому циклу 24 единицы груза.

Полученный план не является оптимальным. Выбираем свободную клетку (3,5), присваиваем ей знак «+» и  переносим по этому циклу 13 единиц груза

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

Сформулируем  двойственную задачу по отношению к  исходной транспортной задаче:

Получим:

       

Экономическая интерпретация двойственной задачи

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