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

                   ⎧ ∂z ∂z ⎫                                                Пусть, например, выпуклый многоугольник АВМСD являет-
     Вектор c = ⎨       ;     ⎬ называется градиентом функции Z.        ся ОДР, а grad Z расположен так, как изображено на рис. 4.4.
                   ⎩ ∂x1 ∂X 2 ⎭
                                                                        Тогда Z принимает максимальное значение в точке М.
Он перпендикулярен линиям уровня и показывает направление
                                                                            Пример 4.3. Фирма выпускает продукцию двух видов: А и В,
                                               ∂z          ∂z           используя два вида взаимозаменяемого оборудования. Фонд вре-
наибольшего возрастания функции Z. Так как         = c1 ,      = c2 ,
                                               ∂x1        ∂X 2          мени работы оборудования ограничен соответственно величина-
                                                                        ми 120 и 260 ч. В таблице приведены нормы затрат времени на
то grad Z = {c1 ; c2 } .
                                                                        изготовление единицы продукции каждого вида:
    Изобразим на одном чертеже ОДР, градиент и одну из линий
уровня (например, c1 x1 + c2 x2 = 0 ) и будем перемещать линию                    Вид продукции          Нормы затрат
                                                                                                                                      Фонд
уровня по ОДР параллельно самой себе в направлении вектора                                                 времени, ч
                                                                                                                                    времени, ч
                                                                         Вид оборудования                А            В
grad Z до тех пор, пока она не пройдет через последнюю (край-
                                                                                     1                   2            4                   120
нюю) ее общую точку с ОДР. Координаты этой точки и являются                          2                   4            2                   260
оптимальным решением данной задачи. Будем обозначать опти-                   Известен план выпуска продукции А и В, составляющий со-
мальное решение X ∗ , а координаты оптимального решения                 ответственно 50 и 70 единиц (перевыполнение плана не предпо-
(плана) x1∗ , x2∗ . Для их нахождения необходимо решить систему         лагается).
                                                                             Определить, сколько единиц продукции А и В должно быть
линейных уравнений, соответствующих прямым, пересекающим-
                                                                        выпущено с использованием оборудования первого и второго ви-
ся в точке оптимума. Подставив координаты x1∗ и x2∗ в функцию           да, чтобы суммарные затраты на выполнение плана были мини-
цели Z, получим Z max = c1 x1∗ + c 2 x 2∗ .                             мальными.
                                                                             Решение. Обозначим через xij количество продукции j-го
                                                                             (     )                                       (
                                                                        вида j = 1,2 , выпускаемой на i-м оборудовании i = 1,2 .      )
                                                                            Условия задачи запишем в виде таблицы:
                                                                                 Вид продукции
                                                                                                                                           Фонд
                                                                                                       А              В
                                                                                                                                          времени
                                                                         Вид оборудования
                                                                                                                 2              4
                                                                                   1                                                        120
                                                                                                      x11                 x12
                                                                                                                 4              2
                                                                                   2                                                        260
                                                                                                      x21                 x22
                                                                                  План                      50             70

        Рис. 4.4. Функция Z принимает максимальное значение
                              в точке М
                                      43                                                                    44