3.1.3. КАНОНИЧЕСКАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования ( КЗЛП).

В канонической форме

1.     все функциональные ограничения записываются в виде равенств с неотрицательной правой частью;

2.     все переменные неотрицательны;

3.     целевая функция подлежит максимизации

Таким образом, КЗЛП имеет вид

                                                                         (3.10)                           

,                                                                         (3.11)         

 

                                        (3.12)                  

или в векторно-матричной форме

                                                                            (3.13)                           

                                                                                                      (3.14)         

                                                                                      (3.15)

КЗЛП является частным случаем общей ЗЛП при m₁=0, p=n

Любую ЗЛП можно привести к каноническому виду, используя следующие правила:

а) максимизация целевой функции = c₁x₁+…+c_nx_n равносильна минимизации целевой функции  -=-c₁x₁ -…-c_nx_n;

б) ограничение в виде неравенства, например, 3Х₁+2Х₂-Х₃£6, может быть приведено к стандартной форме 3Х₁+2Х₂-Х₃+Х₄=6, где новая переменная Х₄  неотрицательна. Ограничение Х₁ -Х₂+3Х₃³10 может быть приведено к стандартной форме Х₁ -Х₂+3Х₃-Х₅=10, где новая переменная Х₅ неотрицательна;

в) если некоторая переменная Х_k может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду , где ³0 и ³0.

 

ДОМАШНЕЕ ЗАДАНИЕ №9

 

Привести к каноническому виду задачи из домашнего задания №1 и №2.

 

 

К оглавлению

Назад к разделу "3.1.2. ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ"

Вперед к разделу "3.2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗЛП"