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

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

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

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

Содержание

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

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

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

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

   Будем считать, что величины запасов к  началу первого месяца y1 и к концу последнего yn+1 заданы.

   Задача  состоит в том, чтобы найти  план производства

                (x1, x2, ..., xn)       (1)

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

             xj + yj - dj = yj+1  j = 1,n     (2)

и минимизируют суммарные затраты за весь планируемый  период

                            (3)

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

   xj ³ 0, yj ³ 0,      j = 1,n     (4)

   Прежде  чем приступить к решению поставленной задачи, заметим, что для любого месяца j величина yj+1 запаса к концу месяца должна удовлетворять ограничениям

            0 £ yj+1 £ dj+1 + dj+2 + ... + dn     (5)

т.е. объем  производимой продукции xj на этапе j может быть настолько велик, что запас yj+1 удовлетворяет спрос на всех последующих этапах, но не

имеет смысла иметь yj+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная xj должна удовлетворять ограничениям

            0 £ xj £ dj + yj+1      (6)

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

Будем решать задачу (1)-(6) методом динамического программирования.

Введем  параметр состояния и составим функцию  состояния.

За параметр состояния  x примем наличный запас в конце k -го месяца

                  x = yk+1      (7)

а функцию  состояния Fk(x) определим как минимальные затраты за первые k месяцев при выполнении условия (5)

                    (8)

где минимум  берется по неотрицательным целым  значениям  x1,...,xk,  удовлетворяющим условиям

                  xj + yj - dj = yj+1  j = 1, k-1     (9)

                  xk + yk - dk = x         (10)

Учитывая, что

   (11)

и величина запаса yk к концу (k-1) периода, как видно из уравнения (10), равна

                  yk = x + dk - xk         (12)

приходим  к рекуррентному соотношению

      

                 (13)

где минимум  берется по единственной переменной xk, которая, согласно (6) может изменяться в пределах

                  0 £ xk £ dk + x        (14)

принимая  целые значения, причем верхняя граница  зависит от значений параметра состояния, изменяющегося в пределах

                  0 £ x £ dk+1 + dk+2 + ... + dn     (15)

а индекс k может принимать значения

            k = 2, 3, 4, ... , n                                       (16)

Если k=1, то

                  F1(x = y2) = min f1(x1, x)     (17) 

                                x1

где

             x1 = x + d1 - y1      (18)

                  0£ x £ d2 + d3 + ... + dn     (19)

т.е. на начальном этапе при фиксированном уровне y1 исходного запаса каждому значению параметра x отвечает только одно значение переменной x1, что несколько уменьшает объем вычислений.

   Применив  известную вычислительную процедуру  динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты xn* оптимального решения, а остальные компоненты определяем как

      

   (20)

Рассмотрим  более подробно функции затрат fj(xj, yj+1) и рекуррентные соотношения. Пусть

              jj(xj) = axj2 + bxj + c

jj (xj) - затраты на производство (закупку) xj единиц продукции на этапе j;

hj - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.

Тогда затраты на производство и хранение на этапе j равны 

            fj(xj, yj+1) = jj(xj) + hj yj+1 = axj2 + bxj + c + hj yj+1.   (21)

Выведенные  ранее рекуррентные соотношения  динамического программирования для  решения задачи управления производством  и запасами в нашем случае принимают  вид:

      (22)

где

            k = 2, 3, ... , n       (23)

            0 £ yk+1 £ dk+1 + dk+1 + ... + dn     (24)

            0 £ xk £ dk + yk+1      (25)

            yk = yk+1 + dk - xk      (26)

Если же k=1, то

Остается  заметить, что полезно обозначить выражение в фигурных скобках  через

          Wk(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk)   (31)

и записать рекуррентное соотношение (22) в виде

            Fk(x=yk+1) = min Wk(xk, yk+1)      (32)

                            xk

где минимум  берется по целочисленной переменной xk, удовлетворяющей условию (25).

   Рассмотрим  трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.

   Пусть спрос (заявки) потребителей на нашу продукцию  составляют: на первый этап d1=2 единицы, на второй – d2=3, на третий -  d3=3 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции на разных этапах различны  и составляют соответственно h1=3, h2=2, h3=3. Затраты на производство xj единиц продукции на j-м этапе определяются функцией

            jj(xj) = 2xj2 + 3xj + 4         (33)

т.е. а=2 b=3; с=4. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

  Исходные  данные задачи можно кратко записать одной строкой:

           d1      d2      d3      a      b      c       h1       h2     h3 y1

           2        3       3    2      3      4   3 2    2 2

  Воспользовавшись  рекуррентными  соотношениями,   последовательно   вычисляем

F1 (x = y2),  F2 (x = y3), ...,  Fk (x = yk+1), ...    и соответственно  находим       1 (x= y2), 2 (x = y3 ), ..., ` k (x = yk+1), ...

   Положим k = 1. Согласно (27) имеем

            (34)

   Учтем, что согласно (28) параметр состояния x = у2 может принимать целые значения на отрезке 0 у2 d2 + d3 , т.е. у2 = 0, 1, 2, 3, 4, 5, 6.

   При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием (29)

   0

х1
2 + у2

   Однако, на первом этапе объем производства х1 не может быть меньше единицы, так как спрос d1 = 2, а исходный запас у1 = 2. Более того, из балансового уравнения

   х1 + у1 - d1 = у2

непосредственно следует, что объем производства связан со значением параметра состояния  x= у2 соотношением

            x1 =  y2 + d1 - y1 = y2 + 2 - 2 = y2     (35)

   В этом и состоит особенность первого этапа. Если задан уровень запаса к  началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому

               F1(x = y2) = W1 (x1, y2

   Придавая  у2 различные целые значения от 0 до 6 и учитывая (35), находим

   y2 = 0, x1 = 0, W1 (0;0) = 02 + 3×0 + 4 + 3×0 = 4

   y2 = 1,  x1 = 1, W1 (1;1) = 12 + 3×1 + 4 + 3×1 = 11

   y2 = 2,  x1 = 2, W1 (2;2) = 22 + 3×2 + 4 + 3×2 = 20

   y2 = 3,  x1 = 3, W1 (3;3) = 32 + 3×3 + 4 + 3×3 = 31

   y2 = 4,  x1 = 4, W1 (4;4) = 42 + 3×4 + 4 + 3×4 = 44

   y2 = 5,  x1 = 5, W1 (5;5) = 52 + 3×5 + 4 + 3×5 = 59

   y2 = 6,  x1 = 6, W1 (6;6) = 62 + 3×6 + 4 + 3×6 = 76

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