Задачи линейного программирования транспортного типа. Горячев Л.В. - 3 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

3
Настоящее методическое пособие предназначено для студентов – слушателей курса "Методы
оптимизации". Вместе с учебно-методическими работами "Практический минимум по методам оп-
тимизации", "Одномерная минимизация", "Выпуклые функции и их свойства"и т.д. оно образует
учебно-методический комплекс для выполнения самостоятельной работы по данному курсу. Рас-
сматриваемая тема относится к числу простых в курсе и поэтому доступна для самостоятельного
изучения даже лишь с помощью данного пособия.
Задачи транспортного типа составляют специальный и довольно обширный класс задач ли-
нейного программирования. Объединяющим признаком этого класса служит наличие особого ти-
па ограничений. Специфичность структуры матрицы условий таких задач делает неэффективным
применение для их решения стандартного симплекс-метода и его математического обеспечения и
требует использования специальных методов. Напомним основные свойства задач линейного про-
граммирования (Л.П.)
Пусть дана задача ЛП в канонической форме: минимизировать линейную форму
n
j=1
c
j
x
j
(1)
при условиях
n
j=1
a
ij
x
j
= b
i
,i=1, 2,...,m (2)
x
j
≥ 0,j=1, 2,...,n (3)
В векторно-матричной форме задача имеет вид
(c, x) − min (1’)
Ax = b (2’)
x ≥ 0 (3’)
Векторы A
j
(j =1, 2,...,n) в матрице A называются векторами условий. Вектор x =(x
1
,x
2
,...,x
n
),
удовлетворяющий условиям (1)-(3), называется планом задачи. Оптимальным планом задачи ЛП
называется план, минимизирующий целевую функцию (1)
План x называется опорным, если векторы A
j
, отвечающие его положительным компонентам,
линейно-независимы. Невырожденный опорный план содержит m положительных компонент, вы-
рожденный опорный план содержит более чем n − m нулевых компонент/
Система линейно-независимых векторов A
j
, отвечающих положительным компонентам опорного
плана, образует его базис. Можно считать, что базис любого опорного плана состоит из m линейно-
независимых векторов.
Сформулируем основные теоремы ЛП, отражающие свойства планов задачи.
Теорема
. Если множество планов задачи (1)–(3) не пусто, то среди них имеется хотя бы один
опорный план.
Теорема
. Если множество планов задачи (1)–(3) не пусто и целевая функция ограничена снизу
на этом множестве, то задача имеет хотя бы один оптимальный опорный план.
Доказательство этих теорем приводится в лекциях. Методы анализа и решения задач ЛП су-
щественно опираются на теорию двойственности. Задача, двойственная к (1)–(3), формулируется
следующим образом: найти вектор y =(y
1
,y
2
,...,y
m
)
T
, максимизирующий линейную форму
m
i=1
b
i
y
i
(4)
при условиях
m
j=1
a
ij
y
i
≤ c
j
,i=1, 2,...,n (5)
или в векторно-матричной форме
(b, y),A
T
y ≤ c
                                                                                                            3

   Настоящее методическое пособие предназначено для студентов – слушателей курса "Методы
оптимизации". Вместе с учебно-методическими работами "Практический минимум по методам оп-
тимизации", "Одномерная минимизация", "Выпуклые функции и их свойства"и т.д. оно образует
учебно-методический комплекс для выполнения самостоятельной работы по данному курсу. Рас-
сматриваемая тема относится к числу простых в курсе и поэтому доступна для самостоятельного
изучения даже лишь с помощью данного пособия.
   Задачи транспортного типа составляют специальный и довольно обширный класс задач ли-
нейного программирования. Объединяющим признаком этого класса служит наличие особого ти-
па ограничений. Специфичность структуры матрицы условий таких задач делает неэффективным
применение для их решения стандартного симплекс-метода и его математического обеспечения и
требует использования специальных методов. Напомним основные свойства задач линейного про-
граммирования (Л.П.)
   Пусть дана задача ЛП в канонической форме: минимизировать линейную форму
                                                      n
                                                      
                                                            cj xj                                         (1)
                                                      j=1

при условиях
                                       n
                                       
                                             aij xj = bi , i = 1, 2, . . . , m                            (2)
                                       j=1

                                             xj ≥ 0, j = 1, 2, . . . , n                                  (3)
В векторно-матричной форме задача имеет вид

                                                   (c, x) − min                                           (1’)

                                                      Ax = b                                              (2’)
                                                       x≥0                                                (3’)
Векторы Aj (j = 1, 2, . . . , n) в матрице A называются векторами условий. Вектор x = (x1 , x2 , . . . , xn ),
удовлетворяющий условиям (1)-(3), называется планом задачи. Оптимальным планом задачи ЛП
называется план, минимизирующий целевую функцию (1)
   План x называется опорным, если векторы Aj , отвечающие его положительным компонентам,
линейно-независимы. Невырожденный опорный план содержит m положительных компонент, вы-
рожденный опорный план содержит более чем n − m нулевых компонент/
   Система линейно-независимых векторов Aj , отвечающих положительным компонентам опорного
плана, образует его базис. Можно считать, что базис любого опорного плана состоит из m линейно-
независимых векторов.
   Сформулируем основные теоремы ЛП, отражающие свойства планов задачи.
   Теорема. Если множество планов задачи (1)–(3) не пусто, то среди них имеется хотя бы один
опорный план.
   Теорема. Если множество планов задачи (1)–(3) не пусто и целевая функция ограничена снизу
на этом множестве, то задача имеет хотя бы один оптимальный опорный план.
   Доказательство этих теорем приводится в лекциях. Методы анализа и решения задач ЛП су-
щественно опираются на теорию двойственности. Задача, двойственная к (1)–(3), формулируется
следующим образом: найти вектор y = (y1 , y2 , . . . , ym )T , максимизирующий линейную форму
                                                      m
                                                      
                                                            bi y i                                        (4)
                                                      i=1

при условиях
                                       m
                                       
                                             aij yi ≤ cj , i = 1, 2, . . . , n                            (5)
                                       j=1

или в векторно-матричной форме
                                                (b, y),     AT y ≤ c

Страницы