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

 

    Обозначим через µ(p1, p2, p3, q1, q2, q3, q4) вектор симплексных множителей (потенциалов). Тогда

                            ∆_ij=µA _ij - c _ij                   i=1, 2, 3          j=1, 2, 3, 4

откуда  следует 

                          ∆_ij=р_i+q_j - c _ij                   i=1, 2, 3          j=1, 2, 3, 4                 (6)

    Значение потенциала р1 выберем произвольно, так как в системе (3) и (4) одно уравнение линейно зависит от остальных. Пусть р1=0. Остальные потенциалы находим из условия, что для базисных клеток ∆_ij=0. Получаем

    ∆₁₁=0,             р1+q1 – c11=0,        0+q1 - 1=0,           q1=1

    ∆₁₂=0,             р1+q2 – c12=0,        0+q2 - 3=0,           q2=3

    ∆₂₂=0,             р2+q2 – c22=0,        p2+3 - 6=0,           p2=3

    ∆₂₃=0,             р2+q3 – c23=0,        3+q3 - 5=0,           q3=2

    ∆₃₃=0,             р3+q3 – c33=0,        p3+2 - 1=0,           p3=-1

    ∆₃₄=0,             р3+q4 – c34=0,      -1+q4 - 3=0,           q4=4

    ∆₃₅=0,             р3+q5 – c35=0,      -1+q5 - 0=0,           q5=1

    Затем по формуле (6) вычисляем оценки всех свободных клеток:

    ∆₁₃=p1+q3 – c13=0+2 – 2=0,    ∆₁₄=0+4 – 5=-1,   ∆₁₅=1+0 – 0=1,

    ∆₂₁=1+3 – 4=0,       ∆₂₄=3+4 – 9=-2,         ∆₂₅=1+3 – 0=4,

    ∆₃₁=1 - 1 – 2=-2,     ∆₃₂=3 - 1 – 4=-2.

    Находим наибольшую положительную оценку

                           max(∆_ij > 0) = 4 = ∆₂₅

    Для найденной свободной клетки строим цикл пересчета. Это будет 25 – 23 – 33 – 35.

    Производим  перераспределение поставок вдоль  цикла пересчета

           ↓                                             

           ↓                                            

 

    ρ_max=12

    Получаем  второе базисное допустимое решение:

    Транспортная  таблица 2

 

    Находим новые потенциалы

    р1=0

    ∆₁₁=0,             р1+q1 – c11=0,        0+q1 - 1=0,           q1=1

    ∆₁₂=0,             р1+q2 – c12=0,        0+q2 - 3=0,           q2=3

    ∆₂₂=0,             р2+q2 – c22=0,        p2+3 - 6=0,           p2=3

    ∆₂₃=0,             р2+q3 – c23=0,        3+q3 - 5=0,           q3=2

    ∆₃₃=0,             р3+q3 – c33=0,        p3+2 - 1=0,           p3=-1

    ∆₃₄=0,             р3+q4 – c34=0,        -1+q4 - 3=0,          q4=4

    ∆₂₅=0,             р2+q5 – c25=0,        3+q5 - 0=0,           q5=-3

      и новые оценки

    ∆₁₃=0+2 – 2=0,    ∆₁₄=0+4 – 5=-1,   ∆₁₅=1+-3 – 0=-3,

    ∆₂₁=1+3 – 4=0,       ∆₂₄=3+4 – 9=-2,

    ∆₃₁=1 - 1 – 2=-2,     ∆₃₂=3 - 1 – 4=-2, ∆₃₅=-3 - 1 – 0=-4.

    Все ∆_ij ≤ 0,                         i=1,2,3;          j=1,2,3,4.

    Таким образом, мы нашли базисное оптимальное решение:

                                 Х= .

    ДИНАМИЧЕСКОЕ  ПРОГРАММИРОВАНИЕ.

    РАСПРЕДЕЛЕНИЕ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ. 

    Производственное  объединение состоит из четырех  предприятий (n=4). Требуется реконструировать предприятия, для чего выделено 700 тыс. руб. (b=700). Обозначим через f_j(x_j) прирост прибыли на j-м предприятии, если оно получит x_j  рублей. Требуется найти такое распределение (х1, х2, х3, х4) капитальных вложений между предприятиями, которое максимизирует суммарный прирост прибыли.

                                  Z = f₁(x1)+ f₂(x2)+ f₃(x3)+ f₄(x4)

при ограничении  по общей сумме капитальных вложений

                                        х1+х2+х3+х4=700.

Выделяемые  предприятиям суммы кратны 100 тыс. руб.

Значения  функции f_j(x_j) приведены в таблице 1.

                                                                                                                 Таблица 1

 

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

    Введем  параметр состояния и определим  функцию состояния. За параметр состояния ξ примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(ξ) определим как максимальную прибыль на первых k предприятиях, если они вместе получают ξ рублей. Параметр ξ может изменяться от 0 до b=700. Если k-е предприятие получит х_k рублей, то остальные ξ- х_k рублей получат предприятия от первого до (k-1)-го так, чтобы была получена максимальная прибыль F_k-1(ξ - х_k.) Тогда прибыль k предприятий будет равна      f_k(х_k)+ F_k-1(ξ - х_k.). Надо выбрать такое значение х_k между 0 и ξ, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению

                    F_k(ξ) = max{ f_k(х_k)+ F_k-1(ξ - х_k)}

                                      0 ≤ х_k ≤ ξ

для k = 2,3,4. Если же k = 1, то

                                          F₁(ξ) = f₁(ξ).

    Для решения задачи заполняем таблицу 2. Значения f₂(х₂) складываем со значениями F₁(ξ – х₂.) = f₁(ξ – х₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение х2(ξ). Заполняем таблицу 3.

                                                                                                                        Таблица 2

 

                                                                                                                   Таблица 3

 

    Продолжая процесс, табулируем функции F₃(ξ), х₃(ξ) 

                                                                                                                        Таблица 4

 

                                                                                                                   Таблица 5