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

Автор работы: Пользователь скрыл имя, 25 Декабря 2013 в 11:08, курсовая работа

Краткое описание

Задача №1(13)
Графическим способом решить задачу линейного программирования ( ). Сформулировать задачу, двойственную по отношению к данной.
Задача 2(63)
На предприятии имеется несколько производственных линий. j-я линия производит в единицу времени единиц продукции i-го типа. Для выполнения задания предприятию необходимо выпускать не менее единиц i-го типа продукции, при этом эксплуатационные расходы j-ой линии составляют млн. рублей в единицу времени. Определить время работы каждой линии для выполнения задания при условии минимизации затрат.

Содержание

Задача 1(13). ….……………………………………………………………..……3
Задача 2(63).………………………………………………………………..……5
Задача 3(113)………………………………………………………………..…..…8

Вложенные файлы: 1 файл

KURSACh_MOJ_13_-_kopia.doc

— 334.50 Кб (Скачать файл)

Содержание

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача №1(13)

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

                          

Решение

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

                        


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

              

.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2(63)

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

Решение:

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

xj–время работы 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 и все приведенные стоимости (коэффициенты при xj в строке z) также неотрицательны. Это значит, что полученный план является оптимальным:

, z*=

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

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

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

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

Найти такую совокупность ui-стоимостей единицы продукции 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 единиц груза

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

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

Получим:

       

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

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

 

 

 

 

 

 

 

 

 

 

 


Информация о работе Методы оптимизации производства