Математическое программирование (линейное программирование). Киселева Э.В - 8 стр.

при ограничениях:                                                                Принимая во внимание условие комплектности, имеем:
                        ⎧m                                                                       a11 x1 + ⋅ ⋅ ⋅ai1 xi + ⋅ ⋅ ⋅ + am1 xm = b1 y ,
                        ⎪ ∑ aij xi ≥ b j    ( j = 1, n),
                        ⎨i =1                                                где y – количество комплектов.
                        ⎪⎩ 0 ≤ xi ≤ d i     (i = 1, m).                           Аналогичные равенства можно записать и для всех осталь-
                                                                             ных видов изделий, т.е. условие комплектности приводит к сис-
                        1.3. Задача о раскрое                                теме ограничений:
     Задача оптимального раскроя материалов заключается в оп-                            a1 j x1 + ... + aij xi + ... + amj xm = b j y ( j = 1,n ).
ределении наиболее рационального способа раскроя имеющегося                  Очевидно,
материала (бревна, стальные полосы, кожа и т.д.), при котором
будет изготовлено наибольшее количество готовых изделий в за-                                      x1 + ... + xi + ... + x m ≤ a
данном ассортименте или будет достигнуто наименьшее количе-                  (на раскрой поступает a единиц сырьевого материала), а также
ство отходов.                                                                                           xi ≥ 0 (i = 1, m).
     Пусть на обработку поступает a единиц сырьевого материа-
                                                                                 Цель задачи – максимизировать количество комплектов:
ла одного вида (например, a бревен одной длины). Из него требу-
ется изготовить комплекты, в каждый из которых входит n видов
                                                                                                       Ζ = y → max .
изделий в количестве, пропорциональном числам b1 , b2 ,..., bn .                 Итак, приходим к математической модели задачи о раскрое:
                                                                                                       Z = y → max ,
Имеется m способов раскроя (обработки) данного материала, т.е.
известны величины aij (i = 1, m; j = 1, n), определяющие коли-                                        ⎧m
                                                                                                      ⎪ ∑ aij xi = b j y ( j = 1, n),
чество единиц j-х изделий при i-м способе раскроя единицы                                             ⎪i =1
                                                                                                      ⎨
сырьевого материала.                                                                                  ⎪m
    Определить план раскроя, обеспечивающий максимальное                                              ⎪ ∑ xi ≤ a,
количество комплектов. Согласно условиям задачи имеем табли-                                          ⎩i =1
цу раскроя:                                                                                                xi ≥ 0 (i = 1, m) .
          Вид изделия
Способ раскроя             1          ...         j             ...    n     Чтобы выразить целевую функцию через переменные x1,…,xm,
          1               a11         ...         a1j           ...   a1n    достаточно воспользоваться любым из соотношений:
          …                ...        ...        ...            ...    ...                                m
          i               ai1         ...        aij            ...   ain                                 ∑ aij xi
          …                ...        ...        ...            ...    ...                         y = i =1             ( j = 1, n).
          m               am1         ...        amj            ...   amn                                  bj
    Пусть xi – количество единиц сырьевого материала, раскраи-
                                                                                                  1.4. Транспортная задача
ваемого i-м вариантом ( i = 1, m) .
                                                                                 Рассмотрим транспортную задачу, т. е. задачу, в которой
    Тогда количество изделий 1-го вида равно:                                речь идет о рациональной перевозке некоторого однородного
                    a11 x1 + ⋅ ⋅ ⋅ai1 xi + ⋅ ⋅ ⋅ + a m1 x m .                продукта от производителей к потребителям.

                                     17                                                                                18