Линейная производственная задача

Автор работы: Пользователь скрыл имя, 17 Ноября 2011 в 09:47, контрольная работа

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

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известны технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор объемов ресурсов В и вектор удельной прибыли С.
Технологическая матрица A, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:
Вектор B объемов ресурсов, каждый элемент которого bi означает предельное количество i-го ресурса для выпуска всего объема продукции:
Вектор удельной прибыли C, элементы которого cj означают прибыль от производства единицы продукции j-го вида:
Количество каждого из товаров задаётся с помощью производственной программы:

Содержание

Линейная производственная задача
Двойственная задача
Задача о «расшивке узких мест производства»
Динамическое программирование. Распределение капитальных вложений
Динамическая задача управления производством и запасами
Анализ доходности и риска финансовых операций

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

Прикладная математика.doc

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

3. Транспортная  задача линейного программирования

  Имеется 3 производителя однородной продукции, имеющие запасы этой продукции 50, 70 и 30 единицы соответственно. Также  имеется 4 потребителя данной продукции. Их потребность составляет 30, 11, 45 и 36 единицы соответственно. Транспортная компания заключила контракт с поставщиками и потребителями на вывоз и поставку данной продукции от производителей к потребителям. При перевозке продукции от каждого производителя к каждому потребителю транспортная компания имеет определённые издержки на единицу продукции: 3 у.е. при перевозке от 1-ого производителя к 1-ому потребителю, 2 у.е. - от 1–ого производителя ко 2-ому потребителю, 6 у.е. – от 1-ого к 3-ему, 7 у.е. – от 1-ого к 4-ому, 7 у.е. – от 2-ого к 1-ому, 8 у.е. – от 2-ого ко 2-ому, 3 у.е. – от 2-ого к 3-ему, 5 у.е. – от 2-ого к 4-ому, 3 у.е. – от 3-его к 1-ому, 3 у.е. – от 3-его ко 2-ому, 4 у.е. – от 3-его к 3-ему, 6 у.е. – от 3-его к 4-ому. Так как естественным стремлением транспортной компании является максимизация прибыли, то требуется составить такой план перевозок, чтобы издержки были минимальными.

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

Предложение производителей и спрос  потребителей можно записать в виде векторов А и B соответственно:    
 

  Требуется найти план перевозок Х = (хij), i = 1,m; j =  1,n  минимизирующий общую стоимость всех перевозок

                                                                    (2)

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

      (3)

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

       (4)

причем по смыслу задачи

х11 > 0 ,. . . .,  xmn > 0.                                              (5)

В нашей  задаче 4 потребителя и 3 поставщика, причём суммарный объем производства Sai = 50 + 70 + 30 = 150 больше, чем требуется всем потребителям Sbi = 30 + 11 + 45 + 36 = 122, т.е. имеем открытую модель транспортной задачи Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 150-122 = 28 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю. Фактически эта потребность будет указывать на количество продукции, которая не будет вывозиться от производителя.

  Обозначим количество перевезённой продукции за x. Таким образом, количество перевезённой продукции от 1-ого производителя к 1-ому потребителю будет , а от 1-ого производителя ко 2-ому потребителю - и т.д. Мы получим матрицу одного размера с С:

  

  Так как нам требуется найти план перевозок, т.е. такие x, чтобы суммарные издержки были минимальными, то выражение, значение которого и есть суммарные издержки (т.е. количество перевезённой продукции помноженное на соответствующие издержки на единицу продукции из матрицы С), должно быть минимальным.

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

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

  Первое  базисное допустимое решение легко  построить по правилу ²северо-западного угла².

потребление B1=30 B2=11 B3=45 B4=36 B5=28  
производство
A1=50 30 3 11 2
9 -
6   7
* +
0 p1=0
         
A2=70   7  
 
8
36 +
3
34 -
5   0 p2=-3
         
A3=30   4   3   4
2 +
6 28 - 0 p3=-2
         
  q1=3 q2=2 q3= 6 q4=8 q5=2  

Пусть p и q – двойственные переменные, соответствующие строкам и столбцам таблицы. Если значения x, p и q - допустимые решения соответствующих двойственных задач, то при равенстве целевых функций эти решения – оптимальны. Для того чтобы целевые функции были равны требуется выполнение условий: для базисных переменных и для свободных переменных ( ). Пусть , тогда (для занятых клеток)

11= p1+q1-C11=0 => q1 =3

12= p1+q2-C12=0 => q2 =2

22= p2+q2-C22=0 => p2 =3-6=-3  и т. д.

Произведем  оценку (для свободных клеток), где  нет поставок: 

14= p1+q4-C14= 0+8-7= 1

15= p1+q5-C15= 0+2-0= 2

21= p2+q1-C21= -3+3-7= -7

22= p2+q2-C22= -3+2-8= -9

25= p2+q5-C25= -3+2-0= -1

31= p3+q1-C31= -2+3-4= -3

32= p3+q2-C32= -2+2-3= -3

33= p3+q3-C33= -2+6-4= 0 

Так как  решение не оптимально поменяем набор  базисных переменных. Для этого выберем  ячейку, которой соответствует максимальная симплекс-разница ∆15. Для того, чтобы не нарушить равновесия воспользуемся методом циклического пересчёта: 1.5 – 3.5 – 3.4 – 2.4 – 2.3 – 1.3 ρ max =9

9       9 - ρ   ρ       9
36 34   36 + ρ 34 - ρ   45 25  
  2 28   2 + ρ 28 - ρ   11 19

Таким образом, сумма в строках и  столбцах осталась неизменной, а мы получили новое базисное решение:

потребление B1=30 B2=11 B3=45 B4=36 B5=28  
производство
A1=50 30 3 11 2   6   7 9 0 p1=0
         
A2=70   7   8 45 3 25 5   0 p2=-1
         
A3=30   4   3   4 11 6 19 0 p3=0
         
  q1=3 q2=2 q3=4 q4=6 q5=0  
 
 
 

Находим новые потенциалы, новые оценки. Пусть , тогда (для занятых клеток) 

11= p1+q1-C11=0 => q1 =3

12= p1+q2-C12=0 => q2 =2 

15= p1+q5-C15=0 => q5 = 0и т. д. p3 = 0, q4 = 6, p2 = -1, q3 = 4

Произведем  оценку (для свободных клеток), где  нет поставок: 

13= p1+q3-C13= 0+4-6= -2

14= p1+q4-C14= 0+6-7= -1

21= p2+q1-C21= -1+3-7= -5

22= p2+q2-C22= -1+2-8= -7

25= p2+q5-C25= -1+0-0= -1

31= p3+q1-C31= 0+3-4= -1

32= p3+q2-C32= 0+2-3= -1

33= p3+q3-C33= 0+4-4= 0 

Данное  базисное решение оптимально, так  как все симплекс разницы   

     Ответ:

 

4. Динамическое программирование. Распределение  капитальных вложений

  Динамическое  программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с n переменными представляется как много шаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

  Рассмотрим  нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fj(xj) прирост мощности  или прибыли на  j-том предприятии, если оно получит xj рублей капвложений. Требуется найти такое распределение (х1, х2, ..., хn) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

  Z=f1(x1)+f2(x2)+...+fn(xn)

  при ограничении по общей сумме капвложений  х1 + х2 +...+хn = b, причём будем считать, что все переменные xj принимают только целые значения xj =1,2,...

  Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоёмкая экономическая задача.

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

  Введём  параметр состояния и определим  функцию состояния. За параметр состояния x  примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x) определим как максимальную прибыль на первых  k  предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие  получит Хк  рублей, то каково бы ни было это значение, остальные xк  рублей естественно распределить между предприятиями от 1-го до (к-1)-го предприятия, чтобы была получена максимальная прибыль Fk-1(x-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x-xk). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:

Информация о работе Линейная производственная задача