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

    Суммарные затраты ресурса Si (i= 1, m) составляют:                    Требуется получить смесь с заданными свойствами при наи-
                                                                      меньших затратах на исходные сырьевые материалы.
                             ai 1 x1 + ⋅ ⋅ ⋅ + ain xn .                   Для составления математической модели запишем условия
    В силу ограниченности ресурса Si величиной bi получим сис-        задачи в виде таблицы:
тему ограничений:
                                                                              Вид вещества         1      ...     j      ...     n    Объем Цена
                  ai 1 x1 + ... + ain xn ≤ bi (i = 1, m) .                                                                            сырья сырья
    На переменные хj должно быть наложено условие неотрица-            Вид сырья
                                                                                 1                a11     ...     a1j    ...   a1n         d1   c1
тельности x j ≥ 0    ( j = 1, n) , т.е. продукция Рj может либо вы-              …                 ...    ...    ...     ...    ...        …    …
пускаться (xj > 0), либо не выпускаться (xj = 0).                                 i               ai1     ...    aij     ...   ain         di   ci
    Итак, математическая модель примет вид:                                      …                 ...    ...    ...     ...    ...        …    …
                                                                                 m                am1     ...    amj     ...   amn         dm   cm
                     Ζ = с1 x1 + ⋅ ⋅ ⋅ + сn xn → max ,                 Минимальное количе-
                        ⎧a11 x1 + ⋅ ⋅ ⋅ + a1n xn ≤ b1 ,                ство вещества в смеси       b1     ...     bj     ...    bn
                        ⎪
                        ⎨L L L L L L
                        ⎪⎩ am1 x1 + ⋅ ⋅ ⋅ + amn xn ≤ bm ,                 Обозначим через хi (i = 1, m) количество сырья i-го вида, вхо-
                                                                      дящего в состав смеси.
                           x j ≥ 0 ( j = 1, n) .                          Цель задачи (целевая функция) – минимизировать суммар-
                                                                      ные затраты на сырье:
                       1.2. Задача о смесях                                               Ζ = с1 x1 + ⋅ ⋅ ⋅ + cm xm → min .
    Задача определения оптимального состава смеси возникает               Система ограничений включает в себя ограничения по тех-
тогда, когда из имеющихся видов сырья путем их смешивания             ническим характеристикам:
необходимо получить конечный продукт с заданными свойства-
ми. К этой группе задач относятся, например, задачи получения                           ⎧a11 x1 + ⋅ ⋅ ⋅ + ai1 xi + ⋅ ⋅ ⋅ + am1 xm ≥ b1 ,
смесей для разных марок бензина в нефтеперерабатывающей                                 ⎪L L L L L L L L L
промышленности, смесей для получения бетона в строительстве,                            ⎪⎪
задача о выборе диеты, составление кормового рациона в живот-                            ⎨ a1 j x1 + ... + aij xi + ... + amj xm ≥ b j ,
новодстве и др. При этом требуется, чтобы стоимость такой сме-                           ⎪L L L L L L L L L
си была минимальной.                                                                     ⎪
    Пусть имеется m видов сырья, запасы которого составляют                              ⎩⎪ a1n x1 + ... + ain xi + ... + amn xm ≥ bn ,
соответственно d1,…, dm. Из этого сырья необходимо составить          а также ограничения по объему сырья, которые с учетом неотри-
смесь, содержащую n веществ, определяющих технические ха-             цательности переменных примут вид:
рактеристики смеси. Известны величины aij (i = 1, m ; j = 1, n) ,                            0 ≤ xi ≤ d i (i = 1, m) .
                                                                           Запишем модель в компактной форме:
определяющие количество j-го вещества в единице i -го вида сы-                                            m

рья, цена которого равна сi (i = 1, m), а также b j ( j = 1, n) −                                 Ζ = ∑ сi xi → min
                                                                                                         i =1
наименьшее допустимое количество j-го вещества в смеси.
                                     15                                                                         16