close

Вход

Забыли?

вход по аккаунту

?

151.Линейное программирование

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Учебное пособие
Составители:
А.Я. Аснина,
Н.Г. Аснина
Издательско-полиграфический центр
Воронежского государственного университета
2011
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Утверждено научно-методическим советом факультета ПММ 25 марта 2011 г.,
протокол № 7
Рецензент канд. физ.-мат. наук, доц. кафедры вычислительной математики
и прикладных информационных технологий Воронежского государственного университета З.А. Шабунина
Учебное пособие подготовлено на кафедре математических методов
исследования операций факультета ПММ Воронежского государственного
университета.
Рекомендуется для студентов 2-го и 3-го курсов специальности «Прикладная математика и информатика» и направления «Бизнес-информатика»
дневной и вечерней формы обучения факультета прикладной математики,
информатики и механики Воронежского государственного университета.
Для специальности 010501 – Прикладная математика и информатика и направления 080700 – Бизнес-информатика
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
Глава 1. Общая постановка задачи линейного программирования.
Графическое решение задач линейного программирования.
Каноническая форма. Базисное решение................................................................4
1.1. Основные определения ........................................................................................4
1.2. Способы записи задачи линейного программирования ...................................5
1.3. Представление экономических задач в виде ЗЛП ............................................6
1.3.1. Задача формирования плана предприятия ...................................................6
1.3.2. Задача о формировании рациона ..................................................................7
1.4. Графический метод решения задачи линейного программирования .............8
Лабораторная работа № 1 ....................................................................................... 13
1.5. Каноническая форма задачи линейного программирования.
Приведение к канонической форме ....................................................................... 14
1.6. Базисное решение ЗЛП.................................................................................... 17
1.7. Перестроение базисного решения ЗЛП .......................................................... 18
Лабораторная работа № 2................................................................................................. 21
Глава 2. Симплекс-метод ........................................................................................ 21
2.1. Основная теорема линейного программирования ......................................... 21
2.2. Алгоритм симплекс-метода ............................................................................. 22
Лабораторная работа № 3................................................................................................. 24
2.3. Симплекс-метод с искусственным базисом ................................................... 24
Лабораторная работа № 4 ....................................................................................... 30
Глава 3. Двойственность в задачах линейного программирования .............. 30
3.1. Основные понятия и определения ................................................................... 30
3.2. Леммы и теоремы двойственности ................................................................. 36
3.3. Экономический смысл двойственной задачи................................................. 40
Лабораторная работа № 5 ....................................................................................... 41
Глава 4. Транспортная задача................................................................................ 41
4.1. Математическая модель транспортной задачи .............................................. 41
4.2. Решение транспортной задачи. Метод потенциалов ..................................... 45
4.3. Транспортные задачи, имеющие усложнения в постановке ........................ 54
Лабораторная работа № 6 ....................................................................................... 60
Список литературы .................................................................................................. 62
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 1
Общая постановка задачи линейного программирования.
Графическое решение задач линейного программирования.
Каноническая форма. Базисное решение
1.1. Основные определения
Задачей линейного программирования (ЗЛП) называется задача вида
a11 x1 + a12 x2 + ... a1n xn ≥ ( ≤ ) b1
a21 x1 + a22 x2 + ... a2 n xn ≥ ( ≤ ) b2
.............................................
am1 x1 + am 2 x2 + ... amn xn ≥ ( ≤ ) bm
(1.1)
x j ≥ 0, ( j = 1, k1 ),
xi ≥ 0, (i = 1, k 2 ),
(1.2)
1 ≤ k1 ≤ k 2 ≤ n.
f ( x) = c1 x1 + c2 x2 + ...cn xn → max
(min)
(1.3)
Система неравенств (1.1) называется системой ограничений задачи.
(1.2) – условие, накладываемое на переменные. Функция (1.3) – функция цели (целевая функция).
⎛ x1 ⎞
⎜ ⎟
⎜x ⎟
Вектор x = ⎜ 2 ⎟ , удовлетворяющий неравенствам (1.1) и (1.2), назыL
⎜ ⎟
⎜x ⎟
⎝ n⎠
вается планом задачи линейного программирования, или допустимым вектором, или допустимым решением.
Множество всех допустимых векторов x будем обозначать буквой G и
называть допустимым множеством или множеством планов.
Вектор x * ∈ G называется оптимальным решением или оптимальным
планом, если для всех x ∈ G : f ( x* ) ≥ f ( x) ( f ( x * ) ≤ f ( x) ).
Если оптимальное решение может быть найдено, то задача называется разрешимой, если же оптимального решения не существует, то задача
называется неразрешимой.
Причины, по которым не может быть найдено оптимальное решение,
следующие.
1. Функция f (x) на допустимом множестве G неограничена. Эта задача называется неразрешимой из-за неограниченности целевой функции.
2. Допустимое множество G пусто ( G = ∅ ), т. е. не существует допустимых решений.
Такая задача называется несовместной.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.2. Способы записи задачи линейного программирования
1.
n
∑a
j =1
ij
x j ≥ (≤)bi , i = 1, m,
x j ≥ 0, ( j = 1, k1 ),
xi ≥ 0, (i = 1, k 2 ),
1 ≤ k1 ≤ k 2 ≤ n.
n
f ( X ) = ∑ c j x j → max .
(min)
j =1
2. Введем вектор aiT = (ai1 , ai2 , ..., ain ) и cT = ( c1 , c2 , ..., cT ) , тогда (1.1)–
(1.3) могут быть записаны в следующем виде:
aiT x ≥ (≤)bi , i = 1, m,
x j ≥ 0, ( j = 1, k1 ),
xi ≥ 0, (i = 1, k 2 ),
1 ≤ k1 ≤ k 2 ≤ n
f ( x) = c T x → max
(min)
⎛ a1 j ⎞
⎛ b1 ⎞
⎜ ⎟
⎜ ⎟
⎜ a2 j ⎟
⎜b ⎟
3. Пусть Aj = ⎜ ⎟ , b = ⎜ 2 ⎟ .
L
⎜L ⎟
⎜ ⎟
⎜b ⎟
⎜a ⎟
⎝ m⎠
⎝ mj ⎠
Тогда (1.1)–(1.3) можно записать в виде
A1 x1 + A2 x2 + ... + An xn ≥ (≤) b ,
x j ≥ 0, ( j = 1, k1 ),
xi ≥ 0, (i = 1, k 2 ),
1 ≤ k1 ≤ k 2 ≤ n
n
f ( x ) = ∑ c j x j → max .
(min)
j =1
⎛ a11a12 ...a1n ⎞
⎜
⎟
..........
......
⎜
⎟
4. Введем матрицу A = ⎜ ai1ai 2 ...ain ⎟ , тогда задача запишется в виде
⎜
⎟
⎜ ................ ⎟
⎜ a a ...a ⎟
⎝ m1 m 2 mn ⎠
Ax ≥ (≤)b ,
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x j ≥ 0, ( j = 1, k1 ),
xi ≥ 0, (i = 1, k 2 ),
1 ≤ k1 ≤ k 2 ≤ n
f ( x) = c T x → max .
(min)
1.3. Представление экономических задач в виде ЗЛП
Многие экономические задачи сводятся к задачам линейного программирования.
Вербальной моделью называется описание на языке предметной области основных свойств и зависимостей исследуемого объекта или проекта.
Математическая модель – это описание с помощью математических символов основных свойств и зависимостей, описанных вербальной моделью.
1.3.1. Задача формирования плана предприятия
Вербальная модель
Имеем предприятие, которое может выпускать n различных видов изделий. Для выпуска данных изделий необходимо m различных видов ресурсов. Пусть bi – лимит i-го ресурса на предприятии, aij – расход i-го ресурса
на единицу j-го вида продукции, cj – прибыль от реализации одной единицы
j-го вида продукции. Требуется сформировать план предприятия, обеспеченный всеми ресурсами и дающий максимально возможную прибыль.
Математическая модель
Формируем план:
x j ≥ 0,
j = 1, n ,
где xj – количество продукции j-го вида в плане, тогда весь план задается
вектором x.
Так как план должен быть обеспечен всеми ресурсами, то получаем
ограничение
n
∑ aij x j ≤ b, i = 1, m . Здесь левая часть неравенства описывает
j =1
количество ресурсов, которое будет израсходовано для выполнения плана x.
При этом при выполнении плана х будет получена прибыль
n
∑c
j =1
j
xj .
Окончательный вид математической модели будет следующий:
n
∑a
j =1
ij
x j ≤ bi , i = 1, m ,
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x j ≥ 0,
j = 1, n ,
n
f ( x) = ∑ c j x j → max
j =1
или
?
??
Ax ≤ b ,
x ≥ 0,
f ( x) = c T x → max .
Задание для самостоятельной работы
Фабрика выпускает продукцию двух видов: П1 и П2. Продукция
обоих видов поступает в оптовую продажу. Для производства этой
продукции используются три исходных продукта: А, В, С. Максимально возможные суточные запасы этих продуктов, расходы продуктов
(сырья) А, В, С на 1 тыс. изделий, а также оптовая цена Z 1 тыс. шт.
изделий П1 и П2 приведены в таблице.
Исходный Расход исходных продуктов на 1
Максимально
продукт
тыс. изделий
возможный запас
(Т)
П1
П2
А
1
2
6
В
2
1
8
С
1
0,8
5
Z
3
2
Какое количество изделий (в тыс. шт.) должна производить
фабрика, чтобы доход от реализации продукции был максимальным?
Запишите математическую модель этой задачи.
1.3.2. Задача о формировании рациона
Вербальная модель
Для составления дневного рациона имеем в наличии n различных
кормов. Для получения сбалансированного рациона (белки, витамины, микроэлементы и др.) необходимо, чтобы в него входило m различных ингредиентов, причем каждый i-й ингредиент должен входить в количестве не
меньше bi ( i = 1, m ), aij – количество i-го ингредиента в одной единице j-го
вида корма, cj – стоимость одной единицы j-го корма.
Требуется сформировать ежедневный рацион так, чтобы он был
обеспечен всеми необходимыми ингредиентами и имел минимальную
стоимость.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Математическая модель
⎛ x1 ⎞
⎜ ⎟
⎜x ⎟
Введем вектор x = ⎜ 2 ⎟ – рацион, где xj – количество j-го вида корма в
L
⎜ ⎟
⎜x ⎟
⎝ n⎠
рационе.
По аналогии с предыдущей задачей математическая модель задачи
формирования рациона будет иметь вид
Ax ≥ b ,
(1.4)
x ≥ 0,
(1.5)
T
(1.6)
f ( x ) = c x → max
Заметим, что полученная математическая модель недостаточно адекватно отражает искомую цель, т.к. в вербальной модели описаны не все необходимые зависимости.
В самом деле, если предположить, что среди выбранных кормов
присутствует, например, прошлогодняя солома, стоимость которой
равна нулю, а все имеющиеся ингредиенты присутствуют в ней в исчезающее малых количествах, то при решении задачи может получиться,
что ежедневный рацион должен состоять только из прошлогодней соломы и составлять, например, пятнадцать тонн, что, разумеется, невозможно.
Отсюда следует, что ограничение (1.5) необходимо заменить на
0 ≤ x ≤ D , где D – вектор верхних границ переменных xj.
?
??
Задание для самостоятельной работы
Если (1.4)–(1.5) оставить в исходном виде, то какие еще «неприятности» мы можем получить в оптимальном плане?
1.4. Графический метод решения задачи линейного
программирования
Если задача линейного программирования имеет две переменные: x1 и
x2, то ее можно решить графически.
Решение задачи происходит в два этапа.
На первом этапе необходимо на плоскости изобразить допустимое
множество, а на втором найти оптимальную точку, если она существует, в
противном случае убедиться в неразрешимости задачи.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Этап 1. Построение допустимого множества
Каждое неравенство в рассматриваемой задаче представляет собой
полуплоскость, а допустимое множество – пересечение этих полуплоскостей. Если неравенства в задаче заменить уравнениями, то получим уравнения прямой. Каждую прямую можно построить по двум точкам. Для того
чтобы выделить необходимую полуплоскость, надо взять точку, не лежащую на прямой, и подставить ее координаты в левую часть неравенства.
Если неравенство выполнено, то выбираем полуплоскость, содержащую
данную точку, в противном случае другую полуплоскость.
Если в задаче присутствуют условия неотрицательности переменных,
то рассматриваем только первый координатный угол.
Если правая часть не равна нулю, то в качестве пробной точки удобнее всего выбрать начало координат (0,0).
Алгоритм выполнения первого этапа
Шаг 1: Выделение первого координатного угла (необязательный).
Шаг 2: i = 1 .
Шаг 3: i-е неравенство записывается как уравнение.
Шаг 4: Полагаем x 11 = 0, x 12 находим из уравнения.
Шаг 5: Полагаем x 22 = 0, x 12 находим из уравнения.
⎛ x11 ⎞
⎛ x12 ⎞
2
Шаг 6: Через точку x = ⎜⎜ 1 ⎟⎟ и x = ⎜⎜ 2 ⎟⎟ проводится прямая.
⎝ x2 ⎠
⎝ x2 ⎠
Шаг 7: В левую часть неравенства подставляется точка с координатами (0,0) . Если неравенство выполнено, то выбирается полуплоскость, содержащая начало координат, в противном случае противоположная полуплоскость.
Шаг 8: Если i < m , то i = i + 1 , переходим к шагу 3, иначе шаг 9.
Шаг 9: Допустимое множество получено. Если оно пустое ( G = ∅ ), то
выписывается ответ: «Задача несовместна, иначе переход к этапу 2».
1
Этап 2. Поиск оптимальной точки
Рассмотрим градиент функции f (x) . Так как функция f (x) линейна,
⎛c ⎞
то ее градиент есть постоянный вектор с координатами Grad ( f ) = ⎜⎜ 1 ⎟⎟ .
⎝ c2 ⎠
Известно, что движение в направлении градиента увеличивает значение функции.
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Прямая, перпендикулярная вектору-градиенту, называется линией
уровня, т.к. значения функции f (x) в любой точке этой прямой одинаковы.
Алгоритм выполнения второго этапа
Шаг 1: Строится вектор-градиент Grad ( f ) = (c1 , c2 ) .
Шаг 2: Кладется линейка перпендикулярно вектору-градиенту.
Шаг 3: Линейка сдвигается параллельно самой себе по направлению
вектора-градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.
Шаг 4: Если при любом положении линейки перпендикулярно вектору-градиенту имеются точки допустимого множества, то выписывается ответ: «Задача неразрешима из-за неограниченности целевой функции, переход к шагу 10». Иначе шаг 5.
Шаг 5: Находится последняя точка допустимого множества, лежащая
на соответствующей линии уровня.
Шаг 6: Если эта точка неединственная, то выбирается точка, которая
является пересечением двух прямых, ограничивающих допустимое множество.
Шаг 7: Выписывается система двух уравнений с двумя неизвестными.
Шаг 8: Из системы уравнений находится оптимальная точка
x * = ( x1* , x2* ) .
Шаг 9: Находится оптимальное значение целевой функции
*
f ( x ) = c1 x1* + c2 x2* .
Шаг 10. Конец.
Замечание. Алгоритм второго этапа рассмотрен в предположении,
что рассматривается максимум целевой функции. Если требуется найти минимум целевой функции, то в шаге 3 требуется сдвигать линейку в направлении, противоположном вектору-градиенту.
Пример 1.1. Решить задачу линейного программирования графически.
2 x1 + 3 x2 ≤ 18 ,
(1.7)
(1.8)
− x1 + 3x2 ≤ 9 ,
2 x1 − x2 ≤ 10 ,
(1.9)
x1 ≥ 0,
T
x2 ≥ 0,
f ( x) = 4 x1 + 2 x2 → max.
Решение. Строим допустимое множество в соответствии с первым этапом алгоритма. В результате получаем ограниченную многогранную область
(рис. 1.1).
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1.1
В табл. 1.1 заданы точки, по которым строятся прямые (1.7)–(1.9).
(1.7)
x1
x2
0
6
(1.8)
9
0
0
3
–9
0
0
–10
Таблица 1.1
(1.9)
5
0
В качестве пробной кочки выбираем начало координат (0, 0).
Для (1.7) 2 ⋅ 0 + 3 ⋅ 0 ≤ 18 . (Верно: выбирается полуплоскость, содержащая начало координат.)
Для (1.8) 0 + 3 ⋅ 0 ≤ 9 . (Верно: выбирается полуплоскость, содержащая
начало координат.)
Для (1.9) 2 ⋅ 0 − 0 ≤ 10 . (Верно: выбирается полуплоскость, содержащая, начало координат.)
⎛ 4⎞
На втором этапе находим Grad ( f ) = ⎜⎜ ⎟⎟ .
⎝ 2⎠
Сдвигаясь по линии уровня в направлении вектора-градиента, получаем оптимальную точку А, находим ее координаты. Так как она является
точкой пересечения прямых (1.7) и (1.9), то решаем систему уравнений:
⎧2 x1 + 3 x 2 = 18,
⎨
⎩2 x1 − x 2 = 10,
x1 = 6,
x 2 = 2.
⎛6⎞
Таким образом, оптимальной точкой x ∗ является точка x ∗ = ⎜⎜ ⎟⎟ .
⎝2⎠
Находим оптимальное значение целевой функции, подставляя значе∗
ние x в функцию:
f ( x ∗ ) = 24 + 4 = 28 .
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 1.2. Решить графически следующую задачу:
3x1 + 2 x 2 ≥ 11,
− 2 x1 + x 2 ≤ 2 ,
x1 − 3x2 ≤ 0 ,
x1 ≥ 0, x 2 ≥ 0 ,
f ( x) = 2 x1 + 4 x 2 → max .
Решение. Построение допустимого множества выполняется так же, как
и в предыдущей задаче (рис. 1.2). В результате получаем неограниченную
многогранную область.
Рис. 1.2
На втором этапе решения параллельным перемещением по линиям
уровня в направлении вектора-градиента устанавливаем, что такое перемещение можно производить неограниченно. Следовательно, целевая функция неограниченна сверху, т.е. f (x) max = ∞ , а сама задача линейного программирования неразрешима из-за неограниченности целевой функции. Заметим, что
если при тех же исходных данных требовалось бы целевую функцию мини*
= (3,1) с
мизировать, то получили бы оптимальное решение в точке xmin
f ( x)*min = 10 .
Пример 1.3. Решить задачу
− x1 + x 2 ≤ 3,
x1 − 2 x 2 ≤ 3,
x1 ≥ 0, x 2 ≥ 0,
(1.10)
(1.11)
f ( x) = − x1 + x2 → max .
Решение. Допустимое множество в данной задаче имеет вид
(рис. 1.3).
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1.3
Из рисунка видно, что допустимое множество неограниченно, однако
оптимальное решение существует, им является луч, выходящий из точки x1max .
Линии уровня целевой функции параллельны прямой − x1 + x2 = 3 , соответствующей первому ограничению. При перемещении линии уровня в направлении вектора-градиента получаем, что линия уровня с максимально возможным значением целевой функции совпадает с прямой: − x1 + x2 = 3 . Таким
образом, целевая функция достигает своего максимального значения
f ( x)*max = 3 во всех точках луча, выходящего из точки x1max = (0, 3) . Задача
имеет бесчисленное множество решений.
Для того чтобы выписать решение в общем виде, возьмем на луче еще
2
одну точку xmax
= (1, 4) . Уравнение луча записывается следующим образом:
*
2
x max
= (1 − λ ) x 1max + λx max
, λ ∈ [0, ∞) .
Таким образом, любое решение данной задачи записывается в виде
*
xmax = (λ , 3 + λ ), λ ∈ [0, ∞) .
Лабораторная работа № 1
Решить задачу линейного программирования графически.
a11 x1 + a12 x2 ≤ b1 ,
a21 x1 + a22 x2 ≤ b2 ,
a31 x1 + a32 x2 ≤ b3 ,
x1 ≥ 0, x2 ≥ 0 ,
f ( x) = c1 x1 + c2 x2 → max .
В табл. 1.2 представлены варианты возможных ограничений и целевых функций.
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таблица 1.2
№
п/п
№
п/п
Ограничения
1
2 x1 + 3 x2 ≤ 18
1
2
− x1 + 3 x2 ≤ 9
2
3
2 x1 − x2 ≤ 10
3
4
x1 + x2 ≥ 2
4
5
6
7
4 x1 − 3 x2 ≤ 12
4 x1 − 3 x2 ≥ 12
x1 + 2 x2 ≤ 6
8
2 x1 − x2 ≤ 8
9
10
2 x1 − x2 ≥ 4
x1 + 2 x2 ≥ 6
Целевая функция
f ( x) = 4 x1 + 2 x 2
f ( x) = 3x1 + x 2
f ( x) = −2 x1 + 7 x2
f ( x) = 5 x1 − x2
x1, 2 ≥ 0
Общее ограничение
В табл.1.3 приведены варианты заданий.
Таблица 1.3
Номер
варианта
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Ограничения
1, 2, 5
1, 2, 8
1, 4, 5
1, 2, 4
1, 5, 10
2, 3, 4
2, 3, 6
1, 4, 8
1, 3, 6
2, 4, 8
2, 5, 8
2, 4, 5
1, 4, 5
1, 4, 6
Целевая
функция
1
2
3
4
1
2
3
4
1
2
3
4
1
2
Номер
варианта
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Ограничения
2, 3, 4
3, 4, 6
1, 6, 10
6, 7, 8
4, 5, 7
1, 4, 6
1, 2, 5
1, 2, 8
1, 2, 4
1, 3, 6
2, 4, 8
2, 3, 6
1, 4, 6
2, 3, 4
Целевая
функция
3
4
1
2
3
4
3
4
3
3
1
1
3
1
1.5. Каноническая форма задачи линейного программирования.
Приведение к канонической форме
ЗЛП называется задачей в канонической форме, если она имеет вид
aiT x = bi ; bi ≥ 0, i = 1, m ,
x ≥ 0,
f ( x) = cT x → max .
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пусть имеется задача линейного программирования:
aiT x ≤ bi ; i = 1, m1 ,
aiT x ≥ bi ; i = m1 + 1, m 2 ,
aiT x = bi ; i = m2 + 1, m .
x j ≥ 0, j = 1, k1 ,
x j ≤ 0, j = k1 + 1, k 2 ,
1 ≤ k1 ≤ k 2 ≤ n .
f ( x) = c T x → max .
(min)
Чтобы привести данную задачу к канонической форме, необходимо
следующее.
1. Если
~
f ( x) = с T x → min ,
то функция заменяется на следующую:
~
f ( x) = − f ( x) = −с T x → max .
2. Для i = 1, m неравенство
aiT x ≤ bi ,
заменяется уравнением
aiT x + xдоп = bi , xдоп ≥ 0 и cдоп = 0 .
3. Для i = 1, m неравенства
aiT x ≥ bi ,
заменяется уравнением
aiT x − xдоп = bi при xдоп ≥ 0 и cдоп = 0 .
Переменная xдоп называется дополнительной переменной и показывает, насколько левая часть неравенства отличается от правой.
4. Если bi ≤ 0 , то обе части соответствующего уравнения умножаются на (–1).
5. Для j = k1 + 1, k 2 вводится новая переменная x 'j = − x j , x 'j ≥ 0 .
6. Для j = k 2 + 1, n переменная x j заменяется разностью двух неотрицательных переменных x j = x1j' − x 2j ' , x1j' ≥ 0, x 2j ' ≥ 0 .
Пример 1.3. Привести ЗЛП к каноническому виду.
2 x1 − x2 + x3 + x4 ≤ 5 ,
x1 − 2 x2 + x3 − x4 = −1,
2 x1
+ x3 + x 4 ≥ 2 ,
x1, 2 ≥ 0, x3 ≤ 0 .
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
~
f ( x) = 5 x1 + x 2 − x3 + 7 x 4 → min .
1. Изменение целевой функции.
2 x1 − x2 + x3 + x4 ≤ 5 ,
x1 − 2 x2 + x3 − x4 = −1,
+ x3 + x 4 ≥ 2 ,
2 x1
x1, 2 ≥ 0, x3 ≤ 0 .
~
f ( x) = −5 x1 − x2 + x3 − 7 x4 → max .
2, 3. Замена неравенств в ограничениях уравнениями.
2 x1 − x2 + x3 + x4 + x1д = 5 ,
x1 − 2 x2 + x3 − x4 = −1 ,
+ x3 + x 4 + x 3 д = 2 ,
2 x1
x1, 2 ≥ 0, x3 ≤ 0, x1д ≥ 0, x2 д ≥ 0 .
~
f ( x) = −5 x1 − x2 + x3 − 7 x4 → max .
4. Устранение неотрицательных чисел в правой части.
2 x1 − x2 + x3 + x4 + x1д = 5 ,
− x1 + 2 x2 − x3 + x4 = 1,
2 x1 + x3 + x4 + x3д = 2 ,
x1, 2 ≥ 0, x3 ≤ 0, x1д ≥ 0, x2 д ≥ 0 .
~
f ( x) = −5 x1 − x2 + x3 − 7 x4 → max .
5. Приведение всех переменных к неотрицательным.
x3 = − x 'j , x4 = x14' − x42 ' .
2 x1 − x2 − x3' + x14 − x42 + x1д = 5 ,
− x1 + 2 x2 + x3' + x14 − x42 = 1 ,
2 x1 − x3' + x14 − x42 + x3д = 2 ,
x1, 2 ≥ 0, x3' ≥ 0, x14 ≥ 0, x42 ≥ 0, x1д ≥ 0, x2 д ≥ 0 .
f ( x) = −5 x1 − x2 − x3' − 7 x14 + 7 x42 → max .
Это окончательный вид ЗЛП.
Заметим, что в соответствующем примере есть первая и третья дополнительные переменные. Для удобства номер дополнительной переменной соответствует номеру строки, в которой она присутствует.
Заметим также, что замена переменной произвольного знака двумя
неотрицательными переменными может привести к неединственному решению, т. к. любое число может быть заменено разностью двух неотрицательных чисел бесчисленным множеством способов. Например, 2 = 0 + 2 ,
2 = 5 − 3 , 2 = 156 − 154 и т. д. Однако при обратной замене этот недостаток
устраняется.
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В дальнейшем почти всегда ЗЛП будут рассматриваться только в канонической форме.
?
??
Задания для самостоятельной работы
1.
Привести ЗЛП к каноническому виду.
− 3x1 − x2 + x4 ≤ 6 ,
x1 + 2 x2 + 4 x3 + x4 ≤ −3 ,
− 2 x1
+ 5 x3 ≥ −2 ,
x1, 2 ≥ 0, x3 ≤ 0 .
2.
3.
~
f ( x) = x1 − 3 x2 − 2 x3 + 8 x4 → max .
5 x1 − 2 x2 − x3 + x4 ≥ −7 ,
2 x1 − 2 x2 − 3x3 ≤ −2 ,
− 3x1 + x2 − 5 x3 = −5 ,
x1, 2 ≥ 0, x3 ≤ 0 .
~
f ( x) = −3 x1 − x2 + 4 x3 + 3x4 → min .
− 3 x 2 − x 3 + 5 x 4 ≤ −2 ,
2 x1
+ 3 x3
≥ 7,
7 x1 + x2 + 2 x3 − x4 ≥ 5 ,
x1 ≥ 0, x2 ,3 ≤ 0 .
~
f ( x) = − x1 + 2 x2 − x3 + 9 x4 → min .
1.6. Базисное решение ЗЛП
Рассмотрим ЗЛП в канонической форме.
Ax = b,
x ≥ 0,
f ( x) = c T x → max ,
(1.12)
где Am×n , m < n .
Будем считать, что rang ( A) = m , т. е. матрица А имеет m линейно независимых столбцов. Допустимое решение x = ( x1 , x2 , ..., xm , 0, 0) , x ∈ G
называется базисным решением или опорным планом, если положительным
значениям xi соответствуют линейно независимые столбцы матрицы А.
Базисное решение имеет не больше чем m положительных компонент.
Если число положительных компонент равно m, то решение называется невырожденным, и соответствующие столбцы матрицы А образуют базис в
m-мерном пространстве. Если число положительных компонент меньше m, то
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
решение называется вырожденным. Тогда, чтобы получить базис, к тем
столбцам, которые соответствуют положительным компонентам, надо добавить столбцы с нулевыми компонентами.
Сформулируем без доказательства.
Утверждение 1. Если ЗЛП разрешима, то для нахождения оптимального решения достаточно перебрать только базисные решения, число которых конечно и не превосходит Сnm .
1.7. Перестроение базисного решения ЗЛП
Рассмотрим сначала способ перестроения базисного решения системы
Ax = b без условия неотрицательности.
Пусть матрица А имеет вид
(
)
~
A= E|A ,
где Е – единичная матрица.
Обозначим через I B множество номеров единичных столбцов матрицы А и через I D множество остальных номеров столбцов. Вектор X пред⎛x ⎞
ставим в виде x = ⎜⎜ B ⎟⎟ , где x B = ( xi ), i ∈ I B и x D = ( xi ), i ∈ I D . Вектор c T
⎝ xD ⎠
представим в виде c T = (c BT , c DT ) . Тогда система примет вид
~
xB + AxD = b .
⎛b⎞
Если положить x D = 0 , то получим базисное решение x = ⎜⎜ ⎟⎟ .
⎝0⎠
Будем получать новое базисное решение, заменяя один из базисных
столбцов на столбец, ранее принадлежащий I D . Это можно сделать с помощью алгоритма Жордана – Гаусса.
Алгоритм Жордана – Гаусса
Пусть выбрано k ∈ I D (номер столбца, который будет вводиться в базис) и alk – направляющий элемент.
Шаг 1: l-строка делится на направляющий элемент.
В новой итерации эта строка будет иметь номер k.
akjн = alj / alk = θ j ,
Шаг 2:
Для i <> k
xkн = xl / alk = θ ,
alk ≠ 0 .
aijн = aij − aikθ j ,
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
xiн = xi − aikθ .
I Bн = ( I B \{l}) ∪ {k} ,
I Dн = ( I D\{k}) ∪ {l} .
Шаг 3:
Алгоритм Жордана – Гаусса не учитывает условия неотрицательности
переменных. Для того чтобы это условие было учтено, надо выбирать k, а
также alk так, чтобы условие неотрицательности сохранилось.
Так как ЗЛП рассматривается в канонической форме, то начальное ба⎛b⎞
зисное решение x = ⎜⎜ ⎟⎟ неотрицательно.
⎝0⎠
Заметим, что если столбец Ak ≤ 0 , то его нельзя вводить в базис, т. к.
при любом выборе направляющего элемента alk x kн = xl / alk < 0 , поэтому
для введения в базис необходимо выбирать столбец Ak , такой, что существует аik > 0 .
Кроме того, как следует из алгоритма Жордана – Гаусса, для i <> k
н
xi = xi − aikθ . Следовательно, необходимо выбрать θ таким образом, чтобы
выполнилось условие: xi − aikθ ≥ 0 для всех i <> k .
Если aik ≤ 0 , то xiн ≥ 0 для любого θ > 0 .
Если aik > 0 , то существует максимальное θ , при котором xiн ≥ 0 . Его
( xi / a ik ) = xl / a lk .
можно найти по правилу θ = min
a >0
ik
Алгоритм перестроения базисного решения ЗЛП
Пусть определен столбец с номером k, у которого существует aik > 0 ,
подлежащий введению в базис.
Шаг 1: Определить l (номер выводимого столбца) по правилу
θ = min
( xi / aik ) = xl / alk .
a >0
ik
Шаг 2: Применить алгоритм Жордана–Гаусса.
Шаг 3: Вычислить значение целевой функции по формуле f ( x) = c BT x B .
Из рассмотренного выше алгоритма следует, что, перебрав с его помощью все базисные решения, можно найти оптимальную точку.
Пример 1.4. Дана ЗЛП в канонической форме. Требуется найти оптимальное решение с помощью перебора базисных решений.
2 x1 + x 2 − x3 + x 4 = 3;
x1 + x 2 + 2 x3
+ x5 = 5;
xi ≥ 0, i = 1,5 ,
f ( x) = 5 x1 + 2 x 2 − x3 − 2 x 4 + x5 → max .
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение. Оформим решение задачи в виде таблицы (табл. 1.4). В первом
столбце поместим текущие базисные переменные, во втором – их коэффициенты в целевой функции, в третьем – базисные координаты текущей точки x B .
Далее переписываем элементы матрицы aij , помещая над каждым столбцом
коэффициент соответствующей переменной в целевой функции. Последний
столбец предназначается для определения значения θ . В последней строке
под x B записывается значение целевой функции, остальные клетки этой
строки пока не заполнены.
Таблица 1.4
5
2
–1
-2
1
A1
A2
A3
A4
A5
3
2
1
–1
1
0
3
5
1
1
2
0
1
5
cB
xB
x4 –2
x5 1
f (x)
x2 2
x5 1
f (x)
B
–1
2
1
–1
1
0
2
–1
0
3
–1
1
5
1
0
2
1
0
1
3
−1
3
2
0
1
1
2
1
0
1
5
0
x3 –1
2
x4
–2
x3 –1
f (x)
x1
5
x3 –1
f (x)
48
5
3
1
7
x5
f (x)
3
3
− 20
3
11
2
5
2
27
−
2
11
5
7
x1
x1 = (0,0,0,3,5)
f ( x 1 ) = −1
x 2 = (0,3,0,0,2)
f (x2 ) = 8
8
11
f (x)
Базисное решение
3
3
2
x2
θ
5
3
−1
3
5
1
2
2
3
1
1
3
0
1
5
2
5
−1
5
1
2
1
2
2
2
5
5
3
1
1
0
1
2
2
−1
5
2
2
1
2
−1
2
11
x 3 = (0,11 , 2 ,0,0)
3 3
3
f ( x ) = 20
3
3
3
5
2
1
3
0
1
11
5
5
x 4 = (0,0, 5 ,11 ,0)
2 2
4
f ( x ) = − 27
2
x 5 = (11 ,0, 7 ,0,0)
5
5
5
48
f (x ) =
5
x 6 = ( 3 ,0,0,0, 7 )
2
2
6
f ( x ) = 11
Перебраны все базисные точки, и оптимальной точкой является
x = ( 3 ,0,0,0, 7 ) со значением f ( x 6 ) = 11 .
2
2
6
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа № 2
Дана ЗЛП:
− x1 + 2 x 2 − x3 + x 4 ≤ 2,
bx1 + x 2 + x3 − 2 x 4 ≤ 12,
2 x1 + cx 2 + 4 x3 + 2 x 4 ≤ 6,
xi ≥ 0, i = 1,4 ,
f ( x) = x1 − x2 − 2 x3 + ax4 → max .
В табл. 1.5 приведены варианты значений параметров a, b, c.
1
2
3
4
5
a
2
3
4
7
8
b
3
1
2
2
3
c
-1
1
-1
3
4
6
7
8
9
10
a
5
4
6
2
5
b
2
3
1
2
3
c
3
6
5
2
7
11
12
13
14
15
a
2
3
5
7
6
b
1
3
2
1
3
c
2
4
-1
5
8
16
17
18
19
20
Таблица 1.5
a
b
c
3
3
1
4
1
2
3
1
0
4
1
3
5
2
6
Необходимо выполнить следующие задания.
1. Привести ЗЛП к канонической форме.
2. С помощью алгоритма перестроения базисного решения ЗЛП найти
четыре различных базисных решения и выбрать среди них наилучшее.
Глава 2
Симплекс-метод
Как было показано выше, с помощью перебора базисных решений
можно получить оптимальное решение, если задача разрешима.
Заметим, что число базисных решений хотя и конечно, однако может
быть весьма большим при больших размерах задачи. Поэтому если имеется
некоторая базисная точка, то хотелось бы знать следующее.
1. Не является ли она оптимальной, и если это так, то просмотр остальных точек не целесообразен.
2. Не является ли задача неразрешимой из-за неограниченности целевой функции. В этом случае просмотр остальных точек также не целесообразен.
3. Если точка неоптимальная, то нельзя ли определить вектор-столбец,
подлежащий введению в базис, такой, что значение целевой функции будет
обязательно больше предыдущего.
2.1. Основная теорема линейного программирования
Пусть дана ЗЛП в канонической форме:
~
xB + AxD = b ,
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x B ≥ 0, x D ≥ 0 .
f ( x) = c BT x B + c DD x D → max .
Эта задача имеет очевидное базисное решение:
⎛ x = b⎞
⎟⎟ ,
xбаз = ⎜⎜ B
0
⎠
⎝
f ( xбаз ) = c BT x B = c DT x D .
Будем называть
Δ j = (c BT A j − c j )
оценкой вектора A j .
(2.1)
⎛ x = b⎞
⎟⎟ со знаТеорема. Пусть имеется базисное решение ЗЛП xбаз = ⎜⎜ B
⎠
⎝0
T
T
чением целевой функции f ( xбаз ) = c B x B = c B b и для всех j найдены оценки
Δ j = (cBT A j − c j ) . Тогда:
1. Если для ∀ j Δ j ≥ 0 , то базисное решение оптимально.
2. Если ∃ Δ k < 0 , то существует бесчисленное множество допустимых
решений x ∈ G , для которых f ( x) > f ( xбаз ) . При этом
2а. Если столбец Ak ≤ 0 , то задача неразрешима из-за неограниченности целевой функции.
2б. Если ∃ aik > 0 , то существует новое базисное решение, значение цеn
) > f ( xбаз ) .
левой функции на котором больше, чем на исходном, т. е. f ( xбаз
Замечание. Теорема справедлива, если базисное решение не вырождено, т. е. b > 0 .
На основе этой теоремы строится метод решения ЗЛП, называемый
симплекс-методом, который фактически является методом перестроения базисного решения с учетом оценок небазисных столбцов.
2.2. Алгоритм симплекс-метода
⎛ x = b⎞
⎟⎟ со значением целевой
Пусть имеется базисное решение xбаз = ⎜⎜ B
0
⎠
⎝
T
функции f ( x) = c B xB .
Шаг 1: Вычислить оценки по формуле
Δ j = ∑ ci aij − c j при всех j.
i∈I B
Шаг 2: Если для ∀ j Δ j ≥ 0 , то выписывается оптимальное решение
задачи.
Конец.
Иначе шаг 3.
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 3: Выбирается Δ k < 0 .
Шаг 4: Просматривается столбец Ak , если Ak ≤ 0 , то выписывается
ответ: «Задача не разрешима из-за неограниченности целевой функции».
Конец.
Иначе шаг 5.
Шаг 5: Алгоритм перестроения базисных решений ЗЛП.
Шаг 6: Переход к шагу 1.
Пример 2.1. Решить задачу
− x1 + x 2 + x3
= 1,
x1 − x 2 +
x4
= 1,
x1 + x 2 +
x5 = 2,
xi ≥ 0, i = 1,5 ,
f ( x) = 2 x1 − x2 + 3 x3 − 2 x4 + x5 → max.
Решение. Оформление задачи происходит аналогично предыдущему
примеру (табл. 2.1).
В последней строке, ранее не заполненной, вписываются оценки и
f ( x B ) , которые вычисляются по формуле f ( x) = (c B , x B ) .
Поскольку на первой итерации Δ 1 < 0 , в базис вводится вектор A1 .
⎧1 2 ⎫
Θ = min ⎨ , ⎬ = 1 , т. е. в качестве направляющего элемента выбирается a21 .
⎩1 1 ⎭
Так как на второй итерации все Δ j ≥ 0 , то конец, получена оптимальная точка x* = (1, 0, 2, 0,1) . Поскольку на небазисных векторах Δ j > 0 , то решение в
задаче единственно.
Таблица 2.1
2
–1
3
–2
1
B
cB
xB
x3
3
x4
x5
A2
A3
A4
A5
1
–1
1
1
0
0
–
–2
1
1
–1
0
1
0
1
1
2
1
1
0
0
1
2
3
–6
7
0
0
0
Δj
x3
3
2
0
0
1
1
0
x1
2
1
1
–1
0
1
0
x5
1
1
0
2
0
–1
1
9
0
1
0
6
0
Δj
θ
A1
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 2.2. Решить задачу
= 1,
⎧− x1 + x2 − x3 + x4
⎪
= 1,
⎨ x1 − x2 + + x5
⎪ x − 3 x + x + + x = 2,
⎩ 1
2
3
6
xi ≥ 0, i = 1,6 ,
f ( x) = 2 x1 − x 2 + x3 + 3x 4 − 2 x5 + x 6 → max .
Решение. Оформление задачи происходит аналогично предыдущему
примеру (табл. 2.2).
Таблица 2.2
B
cB
xB
2
A1
–1
A2
1
A3
3
A4
–2
x4
3
1
–1
1
–1
x5
–2
1
1
–1
x6
1
2
1
3
Δj
A5
1
A6
θ
1
0
0
–
0
0
1
0
1
–3
1
0
0
1
2
–6
3
–3
0
0
0
0
1
0
x4
3
2
0
0
–1
1
x1
2
1
1
–1
0
0
1
1
x6
1
1
0
–2
1
0
–1
9
0
–3
–3
0
6
Δj
0
На второй итерации получаем, что оценка Δ 2 < 0 , но в столбце А2 нет
положительных элементов.
Ответ: целевая функция неограниченна.
Лабораторная работа № 3
Решить симплекс-методом ЗЛП из лабораторной работы № 2.
2.3. Симплекс-метод с искусственным базисом
Вернемся к алгоритму симплекс-метода и заметим, что его применение возможно только при наличии начального базисного решения. Однако
ˆ . В этом
его можно получить, только если матрица А имеет вид A=(E/A)
случае ЗЛП представляется в виде
ˆ = b,
xB + Ax
A
xB ≥ 0, xA ≥ 0,
f ( x) = cBT xB + cAT xA → max
и имеется базисное решение с базисными компонентами x B = b .
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрим задачу.
Ax = b,
x ≥ 0,
(2.2)
f ( x) = c T x → max,
где матрица А не имеет единичных столбцов или их число меньше числа
строк матрицы.
В этом случае нет возможности найти начальное базисное решение,
более того задача (2.2) может оказаться несовместной.
Поэтому задача решается в два этапа. На первом этапе отыскивается
начальное базисное решение, а на втором решается исходная задача с помощью алгоритма симплекс-метода.
Задача первого этапа:
Ax + Ez = b ,
x ≥ 0, z ≥ 0 ,
(2.3)
fˆ( x, z) = − z → max.
∑
i
Переменные zi называются искусственными переменными.
Утверждение 1. Задача (2.3) разрешима.
Утверждение 2. Если при решении задачи (2.3) получено оптимальное решение x0 = ( x 0 , z 0 )T и fˆ( x0 , z0 ) = 0 , то точка x0 = ( x10 , ..., xn0 ) является
допустимым решением задачи (2.3).
Утверждение 3. Если оптимальное значение целевой функции
0
fˆ( x , z0 ) < 0 , то допустимое множество задачи (2.2) пусто.
На основе утверждений 1–3 и строится алгоритм симплекс-метода с
искусственным базисом.
Алгоритм симплекс-метода с искусственным базисом
Шаг 0: Приведение к канонической форме.
Шаг 1: Запись всех исходных данных в таблицу.
Шаг 2: Просмотреть столбцы матрицы A и отыскать единичные
столбцы с единицами в разных позициях. Соответствующие переменные
занести в графу-базис.
Шаг 3: Просматривается базисный столбец, если он заполнен, то переход к алгоритму симплекс-метода.
Конец.
Иначе этап 1.
Этап 1
Шаг 1: Свободные места в базисном столбце заполняются переменными zi с номерами, соответствующими номерам строк.
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 2: Целевые коэффициенты при переменных x j полагаются равными нулю ( c j = 0 ).
Целевые коэффициенты при zi полагаются равными –1 ( ci ( z ) = −1 ).
Шаг 3: Переход к алгоритму симплекс-метода.
Шаг 4: Если fˆ( x )опт < 0 , то выписывается ответ: «Задача несовместна».
Конец.
Иначе переход к этапу 2.
Этап 2
Шаг 1: Для всех переменных x j целевые коэффициенты полагаются
равными c j .
Шаг 2: Переход к алгоритму симплекс-метода.
Конец.
Замечание 1. Единичные столбцы, соответствующие переменным zi ,
в таблицу не заносятся.
Пример 2.3. Решить задачу:
− 2 x1 + x 2 +
x 4 − x5 = 3,
1
2 x1 − x2 + x3 − x 4 − x5 = 1,
2
2
− x1 + x 2 − x3 + x 4 + x5 = 8,
3
x1 ≥ 0 ,
f ( x) = x1 − x2 + x3 − 3 x5 → max .
1. Занесем все данные задачи в табл. 2.3.
Таблица 2.3
B
cв
1
–1
1
0
–3
A1
A2
A3
A4
A5
3
–2
1
0
1
–1
1
2
–1
1
–1
–1⁄2
8
–1
1
–1
xв
2
⁄3
1
1. Просматриваем табл. 2.3 и отыскиваем единичные столбцы для
введения их в базис.
В таблице таких столбцов нет, поэтому в графу В заносят три искусственные переменные, а в графу cв – коэффициент (–1) (табл. 2.4).
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таблица 2.4
0
0
0
0
0
A1
A2
A3
A4
A5
3
–2
1
0
1
–1
–1
1
2
–1
1
–1
–1⁄2
–1
8
–1
1
–1
B
cв
xв
z1
–1
z2
z3
2
⁄3
Ө
1
3. Вычисляем значения целевой функции по формуле f ( x) = ∑ ci xi .
Вычисляем оценки по формуле Δ j = ∑ ci A ij − c j (табл. 2.5).
Таблица 2.5
0
0
0
0
0
A1
A2
A3
A4
A5
3
–2
1
0
1
–1
–1
1
2
–1
1
–1
–1⁄2
–1
8
–1
1
–1
–12
1
–1
–1
B
cв
xв
z1
–1
z2
z3
2
⁄3
Ө
1
–2⁄3
1
⁄2
4. Так как ∆4 < 0, то x4 можно ввести в базис.
xi
Вычисляем θ по формуле θ = min
.
a >0
aik
Минимальному значению θ будет соответствовать место направляющего элемента в столбце x4.
Полностью все шаги перестроения базисного решения представлены
в табл. 2.6. Так как все оценки Δ i ≥ 0 и fˆ( x, z) = 0 , то этап 1 закончен и переходим к этапу 2.
Таблица 2.6
ik
B
cв
xв
0
A1
0
A2
0
A3
0
A4
0
A5
z1
–1
3
–2
1
0
1
–1
z2
z3
–1
–1
1
8
–12
B
cв
xв
2
–1
1
0
A1
–1
1
–1
0
A2
1
–1
–1
0
A3
–1
2
⁄3
2
– ⁄3
0
A4
–1⁄2
1
1
⁄2
0
A5
27
Ө
Ө
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Продолжение табл. 2.6
B
cв
xв
0
A1
0
A2
0
A3
0
A4
0
A5
Ө
x4
z2
0
–1
3
4
–2
0
1
0
0
1
1
0
–1
–3⁄2
–
–
z3
–1
6
1
1
⁄3
–1
0
1
0
–6
0
1
x4
0
–10
39
⁄3
1
– ⁄3
0
– ⁄3
3
5
⁄3
1
– ⁄6
18
9
–
3
z2
–1
4
0
0
1
0
– ⁄2
4
x1
0
18
–4
63
4
30
0
1
0
0
0
1
0
1
0
3
0
1
0
–3
–1
0
1
0
0
0
0
1
0
0
0
5
⁄2
0
–3⁄2
1
⁄2
0
–
x4
x3
x1
0
0
0
3
В верхнюю строку вновь заносим коэффициент c j и в столбец
cв коэффициенты c i при базисных переменных (табл. 2.7).
Таблица 2.7
1
–1
1
0
–3
А1
А2
А3
А4
А5
63
0
3
0
1
0
1
4
0
0
1
0
–3⁄2
1
30
1
1
0
0
1
34
0
2
0
0
2
B
cв
xв
x4
0
x3
x1
⁄2
Так как все оценки больше или равны нулю, следовательно, получено
оптимальное решение:
x * = (30, 0, 4, 63, 0) ,
f ( x * ) = 34 .
Замечание 2. После окончания первого этапа может оказаться, что
все оценки Δ j ≥ 0 , значение целевой функции fˆ( x, z) = 0 , но в базисе сохранились одна или несколько искусственных переменных zi , значения которых равны нулю.
В этом случае непосредственный переход ко второму этапу невозможен, т. к. во втором этапе искусственные переменные должны отсутствовать. Следовательно, их необходимо исключить из базиса. Для этого просматривается вся строка, соответствующая базисному zi .
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если вся строка состоит из нулей, то она вычеркивается, и таблица
второго этапа будет содержать меньшее число строк, что означает, что ранг
исходной матрицы А меньше m.
Если в одной или нескольких строках, соответствующих zi , присутствуют элементы, отличные от нуля, то одна из строк умножается на –1, после этого оценки пересчитываются.
Пример 2.4. Пусть после решения задачи первого этапа имеем табл.
2.8. Здесь значение целевой функции ноль, все оценки больше или равны
нулю, однако среди базисных переменных присутствуют искусственные.
Таблица 2.8
0
0
0
0
A1
A2
A3
A4
----0----
----0----
----0----
----0----
0
0
2
0
–2
0
5
1
0
1
–2
–1
0
0
–2
–1
1
0
0
0
1
1
B
cв
xв
----z1----
----1----
----0----
z2
–1
x1
z3
θ
z2
–1
0
0
–2
0
2
0
x1
0
5
1
0
1
–2
–
z3
–1
0
0
–2
–1
1
0
0
0
4
1
–3
z2
–1
0
0
2
2
0
0
x1
0
5
1
–4
–1
0
–
x4
0
0
0
–2
–1
1
–
0
0
–2
–2
0
x2
0
0
0
1
1
0
x1
0
5
1
0
3
0
x4
0
0
0
0
1
1
0
0
0
0
0
0
Первая строка вычеркивается, а вторая строка умножается на –1. Затем, используя первый этап алгоритма перестроения базисного решения,
находим базис. В результате преобразований искусственные переменные
исключены из базиса. Теперь можно переходить ко второму этапу алгоритма перестроения базисного решения.
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа № 4
Дана ЗЛП
− 2 x1 + x2 +
x4 − x5 ≤ a
2 x1 − x2 + x3 − x4 −
− x1 + x2 − x3 +
b
x5 = 1
b +1
c
x4 + x5 = 8
c +1
j = 1,5 ,
x j ≥ 0,
f ( x) = x1 − x2 + x3 − 3x5 → max .
В табл. 2.9 приведены значения параметров a, b, c.
Задание:
1. Привести ЗЛП к канонической форме.
2. Решить ЗЛП с помощью симплекс-метода с искусственным базисом.
3. Найти оптимальное решение и вычислить значение целевой функции.
Таблица 2.9
Номер
Номер
Номер
Номер
a b c
a b c
a b c
a b c
варианта
варианта
варианта
варианта
1
1 1 2
6
6 2 2
11
2 2 3
16
3 2 4
2
2 1 2
7
7 2 2
12
4 2 3
17
6 2 4
3
3 1 2
8
2 1 3
13
6 2 3
18
3 3 4
4
4 1 2
9
4 1 3
14
3 1 4
19
6 3 4
5
5 2 2
10
6 1 3
15
6 1 4
20
3 4 4
Глава 3
Двойственность в задачах линейного программирования
3.1. Основные понятия и определения
Рассмотрим ЗЛП в общем виде
aiT x ≤ bi ; i = 1, m1 ,
aiT x ≥ bi ; i = m1 + 1, m 2 ,
aiT x = bi ; i = m2 + 1, m .
x j ≥ 0, j = 1, k1 ,
x j ≤ 0, j = k1 + 1, k 2 ,
1 ≤ k1 ≤ k 2 ≤ n .
f ( x) = c T x → max .
(min)
30
(3.1)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Определение 1. Задача
y T A j ≥ c j , j = 1, k1 ,
y T A j ≤ c j , j = k1 + 1, k 2 ,
y T A j = c j , j = k 2 + 1, n .
y j ≥ 0, i = 1, m1 ,
y j ≤ 0, i = m1 + 1, m2
g ( y ) = y T b → min
является двойственной к (3.1).
Основные свойства двойственных задач
1. Количество переменных двойственной задачи совпадает с количеством ограничений исходной задачи.
2. Количество ограничений двойственной задачи совпадает с количеством переменных исходной задачи.
3. Каждому ограничению исходной задачи соответствует переменная
двойственной задачи.
4. Каждой переменной исходной задачи соответствует ограничение
двойственной задачи.
5. Матрица ограничений двойственной задачи является транспонированной по отношению к матрице ограничений исходной задачи.
6. Целевые коэффициенты исходной задачи являются правыми частями ограничений двойственной задачи.
7. Правые части ограничений исходной задачи являются целевыми
коэффициентами двойственной задачи.
8. Если в исходной задаче отыскивается максимум целевой функции,
то в двойственной – минимум.
9. Если в исходной задаче отыскивается минимум целевой функции,
то в двойственной максимум и в ограничениях
y T Aj ≥ c j ,
j = 1, k1
и
y T Aj ≤ c j ,
j = k1 + 1, k 2
меняется знак неравенства на противоположный.
10. Двойственная задача к двойственной задаче совпадает с исходной,
поэтому их называют двойственной парой.
Правила задания знаков ограничений и переменных двойственной задачи можно свести в таблицу (табл. 3.1).
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм построения двойственной задачи
Шаг 1: Каждому ограничению исходной задачи приписывается yi ,
номер которого соответствует номеру ограничения.
Шаг 2: Выписываются в столбик все переменные исходной задачи.
Шаг 3: К каждой переменной x j приписывается ограничение двойственной задачи вида без знака между левой и правой частями
yT f j c j .
Шаг 4: Выписывается целевая функция двойственной задачи
g ( y ) = ( y, b) .
(3.2)
Шаг 5: Знаки ограничений и переменных (3.2), а также ориентация
целевой функции выписываются в соответствии с табл. 3.1.
Таблица 3.1
Правила задания знаков ограничений и переменных двойственной задачи
Целевая функция
Целевая функция
→
min
Переменные
≤
≥
=
≥0
≤0
Ограничения
Переменные
Ограничения
→
max
Произвольный знак
≥0
≤0
Произвольный знак
≥
≤
=
Пример 3.1. Дана ЗЛП:
3 x1 − 2 x 2 + x3 − x 4 ≤ 5,
− x1 + 3 x 2 + x3 + 2 x 4 ≥ 4,
x1 + 2 x 2 − x3 − 3 x 4 = 6,
x1, 2 ≥ 0, x3 ≤ 0 ,
fˆ( x) = 5 x + 3 x − 4 x → min .
1
2
3
1
2
3
Каждому ограничению приписываем двойственную переменную yi :
y1 3x1 − 2 x 2 + x3 − x4 ≤ 5 ,
y2 − x1 + 3x2 + x3 + 2 x4 ≥ 4 ,
y3 x1 + 2 x2 − x3 − 3x4 = 6 ,
x1, 2 ≥ 0, x3 ≤ 0 ,
fˆ( x) = 5 x + 3 x − 4 x → min .
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Выписываются все переменные двойственной задачи, и к ним приписываются ограничения двойственной. Значение знаков ограничений и знаков переменных выписывается в соответствии с табл. 3.1.
x1 3 y1 − y 2 + y3 ≤ 5 ,
x2 − 2 y1 + 3 y 2 + 2 y3 ≤ 3 ,
x3 y1 + y 2 − y3 ≥ −4 ,
x4 − y1 + 2 y 2 − 3 y3 = 0 ,
y1 ≤ 0, y 2 ≥ 0 .
Целевая функция двойственной задачи имеет вид
g ( y ) = 5 x1 + 4 x2 + 6 x3 → max .
Окончательный вид двойственной задачи следующий:
x1 3 y1 − y 2 + y3 ≤ 5 ,
x2 − 2 y1 + 3 y 2 + 2 y3 ≤ 3 ,
x3 y1 + y 2 − y3 ≥ −4 ,
x4 − y1 + 2 y 2 − 3 y3 = 0 ,
y1 ≤ 0, y 2 ≥ 0 .
g ( y ) = 5 x1 + 4 x2 + 6 x3 → max .
Пример 3.2. Дана ЗЛП:
3 x1 − 2 x 2 + x3 − x 4 ≤ 5,
− x1 + 3 x 2 + x3 + 2 x 4 ≥ 4,
x1 + 2 x 2 − x3 − 3 x 4 = 6,
x1, 2 ≥ 0, x3 ≤ 0 ,
fˆ( x) = −3 x + 4 x + 2 x → max .
1
2
3
Каждому ограничению приписываем двойственную переменную yi :
y1 3x1 − 2 x 2 + x3 − x4 ≤ 5 ,
y2 − x1 + 3x2 + x3 + 2 x4 ≥ 4 ,
y3 x1 + 2 x2 − x3 − 3x4 = 6 ,
x1, 2 ≥ 0, x3 ≤ 0 ,
fˆ( x) = −3 x + 4 x + 2 x → max .
1
2
3
Выписываются все переменные двойственной задачи, и к ним приписываются ограничения двойственной. Значение знаков ограничений и знаков переменных выписывается в соответствии с табл. 3.1.
x1 3 y1 − y 2 + y3 ≥ −3 ,
x2 − 2 y1 + 3 y 2 + 2 y3 ≥ 4 ,
x3 y1 + y 2 − y3 ≤ 2 ,
x4 − y1 + 2 y 2 − 3 y3 = 0 ,
y1 ≥ 0, y 2 ≤ 0 .
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Целевая функция двойственной задачи имеет вид
g ( y ) = 5 x1 + 4 x2 + 6 x3 → min .
Окончательный вид двойственной задачи следующий:
x1 3 y1 − y 2 + y3 ≥ −3 ,
x2 − 2 y1 + 3 y 2 + 2 y3 ≥ 4 ,
x3 y1 + y 2 − y3 ≤ 2 ,
x4 − y1 + 2 y 2 − 3 y3 = 0 ,
y1 ≥ 0, y 2 ≤ 0 .
g( y) = 5 x1 + 4 x2 + 6 x3 → min.
Замечание. Если ЗЛП задана в канонической форме
Ax = b,
x ≥ 0,
f ( x) = cT x → max,
то очевидно, что двойственная к ней имеет вид:
yT A ≥ cT ,
g( y) = yT b → min.
Рассмотрим теперь ЗЛП следующего вида:
Ax ≤ b,
(3.3)
x ≥ 0,
f ( x) = cT x → max,
b ≥ 0.
Такая задача называется задачей в симметричной форме. Можно заметить,
что приведенная выше задача формирования плана предприятия имеет
именно симметричную форму.
Как следует из алгоритма построения двойственной задачи, двойственная задача к ЗЛП в симметричной форме имеет следующий вид:
y T A ≥ cT ,
y ≥ 0,
g( y) = yT b → min.
Поэтому если задана задача в произвольной форме, то ее можно привести к виду, объединяющему каноническую и симметричную формы, т. е.
к виду, в котором все ограничения являются либо равенствами, либо неравенствами вида « ≤ », все переменные неотрицательны, а в целевой функции
ищется максимум. И тогда двойственную задачу можно выписать, не используя табл. 3.1.
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм преобразования исходной задачи
Шаг 1: Просматриваются ограничения задачи, и если среди ограничений имеются ограничения типа больше или равно, то коэффициенты умножаются на –1 и знак неравенства изменяется на противоположный.
Шаг 2: Рассматривается целевая функция. Если в исходной задаче
требуется найти ее минимум, то все коэффициенты умножаются на –1, а
функцию переориентируют на максимум.
Пример 3.3. Дана ЗЛП:
3x1 − 2 x 2 + x3 − x 4 ≤ 5,
(3.4)
(3.5)
− x1 + 3x 2 + x3 + 2 x 4 ≥ 4,
(3.6)
x1 + 2 x 2 − x3 − 3x 4 = 6,
x j ≥ 0,
j = 1,4 ,
fˆ( x) = 5 x1 + 3 x2 − 4 x3 → min .
Ограничение задачи (3.5) является ограничением типа «больше или
равно», и в соответствии с алгоритмом его необходимо заменить ограничением «меньше или равно».
Целевая функция ориентирована на минимум, в соответствии с алгоритмом ее необходимо заменить функцией, ориентированной на максимум.
Окончательный вид задачи, для которой будем строить двойственную, следующий:
3 x1 − 2 x2 + x3 − x4 ≤ 5,
(3.4)
x1 − 3 x2 − x3 − 2 x4 ≤ −4,
(3.5)
(3.6)
x1 + 2 x2 − x3 − 3 x4 = 6,
x j ≥ 0, j = 1,4 ,
f ( x) = −5 x1 − 3 x2 + 4 x3 → max.
Каждому ограничению приписываем двойственную переменную yi :
y1 3x1 − 2 x 2 + x3 − x 4 ≤ 5 ,
y2 x1 − 3 x 2 − x3 − 2 x 4 ≤ −4 ,
y3 x1 + 2 x 2 − x3 − 3x 4 = 6 ,
x j ≥ 0, j = 1,4 ,
f ( x) = −5 x1 − 3 x2 + 4 x3 → max.
Выписываются все переменные двойственной задачи, и к ним приписываются ограничения двойственной:
x1 3 y1 + y 2 + y 3 ≥ −5 ,
x2 − 2 y1 − 3 y 2 + 2 y 3 ≥ −3 ,
x3 y1 − y 2 − y3 ≥ 4 ,
x4 − y1 − 2 y2 − 3 y3 ≥ 0.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В соответствии с алгоритмом условие типа y i ≥ 0 накладывается на
первую и вторую двойственные переменные: y1 ≥ 0, y 2 ≥ 0.
Целевая функция двойственной задачи имеет вид
g( y) = 5 y1 − 4 y2 + 6 y3 → min.
Окончательный вид двойственной задачи следующий:
3 y1 + y 2 + y 3 ≥ −5 ,
− 2 y1 − 3 y 2 + 2 y 3 ≥ −3 ,
y1 − y 2 − y3 ≥ 4 ,
− y1 − 2 y 2 − 3 y3 ≥ 0 ,
y1 ≥ 0, y 2 ≥ 0 ,
g ( y ) = 5 y1 − 4 y 2 + 6 y 3 → min .
3.2. Леммы и теоремы двойственности
~
Лемма 1. Пусть G – допустимое множество исходной задачи и G –
~
допустимое множество двойственной задачи. Тогда для всех х ∈ G и y ∈ G
выполняется следующее неравенство:
f ( x) ≤ g ( y ) .
Лемма 2. Если одна из задач двойственной пары неразрешима из-за
неограниченности целевой функции, то другая несовместна.
~
Лемма 3. Если G ≠ ∅ и G ≠ ∅ , то обе задачи разрешимы.
~
Лемма 4. Пусть x * ∈ G и y * ∈ G таковы, что
f (x* ) = g ( y * ) ,
тогда x * и y * – оптимальные решения исходной и двойственной задач соответственно.
Первая теорема двойственности. Если одна из задач двойственной
пары разрешима, то разрешима и другая задача. При этом значение целевой функции на оптимальных решениях исходной и двойственной задач
совпадают:
f (x* ) = g ( y * ) ,
где x * и y * – оптимальные решения исходной и двойственной задач соответственно.
~
Вторая теорема двойственности. Пусть G ≠ ∅ и G ≠ ∅ . Для того
~
чтобы x * ∈ G и y * ∈ G были оптимальными решениями исходной и двойственной задач соответственно, необходимо и достаточно выполнение следующих условий:
( y * ) T ( Ax * − b) = 0 ,
(3.7)
* T
T
*
(( y ) A − c ) x = 0 .
(3.8)
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Следствие из второй теоремы двойственности. Пусть x * и y * –
оптимальные решения исходной и двойственной задач соответственно. Тогда если на оптимальном решении исходной задачи какое-либо ограничение
выполняется как строгое неравенство, то соответствующая двойственная
переменная равна нулю.
Если оптимальная переменная исходной задачи отлична от нуля, то
соответствующее двойственное ограничение на оптимальном решении выполняется как строгое равенство.
Используя следствие ко второй теореме двойственности, можно,
имея оптимальное решение исходной задачи, найти оптимальное решение
двойственной задачи.
Алгоритм решения двойственной задачи
Шаг 1. Выписывается двойственная задача (см. алгоритм построения
двойственной задачи).
Шаг 2. Просматриваются переменные исходной задачи.
Если переменные строго больше нуля, то соответствующее ограничение
двойственной задачи записывается как равенство.
Шаг 3. Значения переменных исходной задачи подставляются поочередно в левую часть каждого ограничения этой задачи. Полученное значение сравнивается с правой частью. Если получено строгое неравенство, то соответствующая переменная двойственной задачи полагается равной нулю.
Шаг 4. Решается полученная система линейных уравнений относительно двойственных переменных yi . Решение этой системы есть оптимальное решение двойственной задачи.
Шаг 5. Вычисляется значение целевой функции g ( y * ) . Оно должно
получиться равным f ( y * ) .
Рассмотрим пример, используя условие и решение примера 1.1.
Пример 3.4. Дана ЗЛП и ее оптимальное решение:
2 x1 + 3 x2 ≤ 18 ,
(3.9)
− x1 + 3 x2 ≤ 9 ,
(3.10)
2 x1 − x2 ≤ 10 ,
(3.11)
x1 ≥ 0,
x2 ≥ 0,
f ( x) = 4 x1 + 2 x2 → max ,
⎛6⎞
x ∗ = ⎜⎜ ⎟⎟ , f ( x ∗ ) = 24 + 4 = 28 .
⎝ 2⎠
Требуется записать двойственную задачу и найти ее решение.
Решение. Выпишем исходную задачу и припишем к ее ограничениям
слева двойственные переменные:
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
y1 2 x1 + 3x2 ≤ 18 ,
y2 − x1 + 3x 2 ≤ 9 ,
y3
2 x1 − x 2 ≤ 10 .
x1 ≥ 0,
x2 ≥ 0,
f ( x) = 4 x1 + 2 x 2 → max .
Двойственная задача:
x1
2 y1 − y2 + 2 y3 ≥ 4 ,
x2
3 y1 + 3 y 2 − y 3 ≥ 2,
y1, 2,3 ≥ 0 ,
g ( y ) = 18 y1 + 9 y 2 + 10 y3 .
Так как x1* = 6 > 0 и x = 2 > 0 , следовательно, оба ограничения двойственной задачи записываются как строгие равенства:
2 y1 − y2 + 2 y3 = 4 ,
3 y1 + 3 y2 − y3 = 2 .
Подставим x * поочередно в каждое из неравенств исходной задачи:
*
2
2 ⋅ 6 + 3 ⋅ 2 = 18 = 18 ,
− 1 ⋅ 6 + 3 ⋅ 2 = 0 < 9 , следовательно, y2 = 0 ,
2 ⋅ 6 − 2 = 10 = 10 .
Таким образом, для нахождения оптимального решения двойственной
задачи имеем систему
⎧ y1 = 1,
⎧2 y1 − y 2 + 2 y 3 = 4,
⎪
⎪
⎨3 y1 + 3 y 2 − y 3 = 2, ⇒ ⎨ y 2 = 0,
⎪ y = 1.
⎪ y = 0,
⎩ 3
⎩ 2
⎛1 ⎞
⎜ ⎟
То есть y = ⎜ 0 ⎟ .
⎜1 ⎟
⎝ ⎠
*
Вычислим значение целевой функции g ( y * ) = 18 ⋅ 1 + 9 ⋅ 0 + 10 ⋅ 1 = 28 , из
чего следует g ( y * ) = f ( x * ) .
Замечание. Может оказаться, что в оптимальной точке исходной задачи
переменных не две, а три прямые. Тогда система уравнений для решения
двойственной задачи будет иметь переменных больше, чем ограничений. Это
означает, что двойственная задача имеет не единственное решение.
Пример 3.5. Дана ЗЛП и ее оптимальное решение:
2 x1 + 3x2 ≤ 18 ,
− x1 + 6 x2 ≤ 6 ,
2 x1 − 3x2 ≤ 6 .
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x1, 2 ≥ 0 ,
f ( x) = 4 x1 + 2 x 2 → max ,
⎛6⎞
x ∗ = ⎜⎜ ⎟⎟ , f ( x ∗ ) = 24 + 4 = 28 .
⎝ 2⎠
Требуется записать двойственную задачу и найти ее решение.
Решение. Выпишем исходную задачу и припишем к ее ограничениям
слева двойственные переменные:
y1
2 x1 + 3 x2 ≤ 18 ,
y2
− x1 + 6 x2 ≤ 6 ,
y3
2 x1 − 3 x2 ≤ 6 .
x1, 2 ≥ 0 ,
. f ( x) = 4 x1 + 2 x2 → max.
Двойственная задача:
x1 2 y1 − y 2 + 2 y 3 ≥ 4 ,
x 2 3 y1 + 6 y 2 − 3 y3 ≥ 2,
y1, 2 ,3 ≥ 0 ,
g( y) = 18 y1 + 6 y2 + 6 y3 → min.
Так как x1* = 6 > 0 и x 2* = 2 > 0 , следовательно, оба ограничения двойственной задачи записываются как строгие равенства:
2 y1 − y 2 + 2 y 3 = 4 ,
3 y1 + 6 y 2 − 3 y3 = 2 .
Подставим x * поочередно в каждое из неравенств исходной задачи:
2 ⋅ 6 + 3 ⋅ 2 = 18 = 18 ,
−1⋅ 6 + 6 ⋅ 2 = 6 ,
2⋅6 − 3⋅ 2 = 6.
Из этого следует, что ни одну из переменных двойственной задачи
нельзя приравнять к нулю, следовательно, имеем два уравнения с тремя неизвестными.
Таким образом, для нахождения оптимального решения двойственной
задачи имеем систему с тремя неизвестными:
⎧2 y1 − y 2 + 2 y3 = 4,
⎨
⎩3 y1 + 6 y 2 − 3 y3 = 2.
Решим ее. Умножим первое уравнение системы на 6 и сложим со
вторым.
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
26 3
26 3
⎧
⎧
− y3 ,
− y3 ,
y1 =
y1 =
⎪
⎪
⎧15 y1 = 26 − 9 y3 ,
⎪
⎪
15 5
15 5
⎨
⎨
⎨
⎩ y 2 = 2 y1 − 4 + 2 y3 , ⎪ y = 52 + 6 y − 4 + 2 y , ⎪ y = − 8 + 4 y .
3
3
⎪⎩ 2 15 5 3
⎪⎩ 2
15 5
26
2
26 3
8 4
− y3 ≥ 0 , − + y3 ≥ 0 , то y3 ≤
и y3 ≥ ,
Так как y3 ≥ 0 и
9
3
15 5
15 5
⎡2 8⎤
следовательно y3 ∈ ⎢ ; 2 ⎥ .
⎣3 9⎦
Вычислим значение целевой функции
⎛ 26 3 ⎞ ⎛ 8 4 ⎞
g ( y * ) = 18 ⋅ ⎜ − y3 ⎟ + 6⎜ − + y3 ⎟ + 6 y3 = 28 ,
⎝ 15 5 ⎠ ⎝ 15 5 ⎠
*
*
из чего следует g ( y ) = f ( x ) .
8 4
⎡2 8⎤
⎛ 26 3
⎞
То есть y * = ⎜ − y3 ; − + y3 ; y3 ⎟ , где y3 ∈ ⎢ ; 2 ⎥ .
15 5
⎣3 9⎦
⎝ 15 5
⎠
3.3. Экономический смысл двойственной задачи
Рассмотрим задачу формирования плана предприятия из первой главы:
n
∑a
j =1
x j ≤ bi ,
ij
x j ≥ 0,
j = 1, n ,
n
f ( x) = ∑ c j x j → max ,
j =1
где bi – лимит i-го ресурса на предприятии,
aij – расход i-го ресурса на единицу j-го вида продукции,
cj – прибыль от реализации одной единицы j-го вида продукции,
n – количество изделий, которые может выпустить предприятие,
m – количество ресурсов,
xj – количество продукции j-го вида в плане.
Заметим, что задача формирования плана является ЗЛП в симметричной форме, поэтому двойственная к ней задача имеет вид
m
∑a
i =1
ij
yi ≥ c j ,
yi ≥ 0, i = 1, m ,
m
g ( y ) = ∑ bi yi → min .
i =1
Для того чтобы понять экономический смысл двойственности, введем
наименование всех параметров исходной задачи.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
хj – шт,
bi – кВт/ч,
кВт ч
,
аij –
шт
с j – руб. /шт.,
и т. к. в двойственной задаче наименование левой и правой частей должны
совпадать,
руб.
руб.
кВт ч
y=
.
, откуда y =
шт
кВт ч
шт
Таким образом, переменная получает смысл цены единицы ресурса. Однако надо помнить, что двойственная переменная есть цена ресурса только в
рамках рассматриваемой задачи, поэтому лауреатом Нобелевской премии
Л. В. Канторовичем двойственные переменные были названы объективно обусловленными оценками. Кроме того, т. к. на оптимальном решении
f ( x* ) = g ( y * ) ,
n
m
j =1
i =1
∑ c j x*j = ∑ bi yi* ,
то значение двойственной переменной yi* показывает, насколько увеличится суммарная прибыль. Если количество соответствующего ресурса увеличится на одну единицу, то yi* есть мера дефицитности i-го ресурса.
Лабораторная работа № 5
Используя данные, полученные в ходе выполнения своего варианта из
лабораторной работы № 1, выполнить следующие задания.
1. Выписать двойственную задачу.
2. Найти ее решение.
Глава 4
Транспортная задача
4.1. Математическая модель транспортной задачи
Вербальная модель
Имеется m поставщиков некоторого продукта. Ai ( i = 1, m ) – количество продукта у i-го поставщика.
Имеется n потребителей этого продукта. Bj ( j = 1, n ) – потребность jго потребителя.
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
сij – затраты на перевозку единицы продукта (1 т, 1 кг, 1 банка и т.д.)
от i-го поставщика к j-му потребителю.
Требуется составить план перевозки продукции от поставщиков к потребителям так, чтобы суммарные затраты на перевозку были минимальными (имеется в виду, что перевозки осуществляет одна фирма).
Предполагается выполнение условия баланса:
m
n
i =1
j =1
∑ Ai = ∑ B j ,
т. е. суммарное наличие продукта у всех поставщиков равно суммарной потребности всех потребителей.
Математическая модель
Пусть xij ≥ 0 – количество продукции, которое перевозят от i-го поставщика к j-му потребителю.
Так как считается выполненным условие баланса
m
n
∑A = ∑B
i
i =1
j =1
j
,
(4.1)
то возникают ограничения:
1) от каждого поставщика должна быть вывезена вся продукция
n
∑x
j =1
ij
= Ai , i = 1, m ,
(4.2)
2) каждый потребитель должен быть удовлетворен, т.е. должно быть
перевезено столько продукции, сколько нужно, ни больше, ни меньше.
m
∑x
i =1
ij
= B j , j = 1, n .
(4.3)
Целевая функция будет выглядеть следующим образом:
m
n
C ( x) = ∑∑ cij xij → min .
(4.4)
i =1 j =1
Как видно из математической модели, транспортная задача представляет собой ЗЛП в канонической форме, имеющую (n + m) ограничений и (n × m)
переменных. То есть транспортная задача даже при небольшом количестве
поставщиков и потребителей оказывается достаточно громоздкой, и ее решение с помощью обычного симплекс-метода хотя и возможно, но требует значительных информационных и временных ресурсов. Однако с учетом специфики системы ограничений формулы симплекс-метода значительно упрощаются. Модифицированный с учетом структуры матрицы симплекс-метод называется методом потенциалов и будет рассматриваться позже.
Способ задания
Для решения любой ЗЛП ее необходимо представить в виде таблицы, в
которую заносят все данные, отличающие одну задачу от другой. В частности
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
для ЗЛП общего вида, представленной в канонической форме, должна быть
задана таблица из (m + 1) строк и (n + 1) столбцов, где в первый столбец x B
заносятся правые части системы ограничений, а в дальнейшем базисные компоненты текущего базисного решения. В остальные столбцы заносятся столбцы матрицы А, а в первую строку коэффициенты целевой функции.
Заметим, что условие неотрицательности переменных в таблице не
отражается, т. к. предполагается выполненным для всех ЗЛП. Что же касается транспортной задачи, то Pij – столбцы ее матрицы ограничений имеют
«длину» (n + m) и состоят из двух блоков. Первый блок «длины» m имеет
единицу на месте i и нули на остальных местах, а второй блок «длины» n
имеет единицу на месте j и нули на остальных:
⎛0 ⎞
⎜L ⎟
⎜1(i ) ⎟
⎜L ⎟
⎜0 ⎟
Pij = ⎜
⎟.
0
⎟
⎜
⎜L ⎟
⎜1( j ) ⎟
⎜L ⎟
⎝0 ⎠
Таким образом, если известно число поставщиков и потребителей, то
вид столбца Pij известен, и при записи исходных данных его можно не учитывать. Поэтому транспортная задача задается таблицей размера
( (m + 1) × (n + 1) ), где в первом блоке матрицы размером ( m × n ) выписывается матрица коэффициентов целевой функции C = cij . Справа выписывается столбец со значениями Ai , а внизу – B j (рис. 4.1).
j
i
1
…
j
…
n
Ai
с11
с1 j
с1n
A1
сi1
сij
сin
Ai
сm1
сmj
сmn
Am
Bj B1
Bj
Bn
1
M
i
M
m
Рис. 4.1.
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Допустимое решение X = {xij } также заносится в матрицу размером
( m × n ). При этом i-я строка соответствует i-му ограничению (1), а j-й столбец – j-му ограничению (2). Откуда следует, что сумма элементов i-й строки
матрицы X равна Аi , сумма всех элементов j-го столбца равна B j (рис. 4.2).
j
i
1
1
…
j
…
n
x11
x1 j
x1n
A1
xi1
xij
xin
Ai
xm1
xmj
xmn
Am
B1
Bj
Bn
M
i
M
m
Рис. 4.2.
Анализ транспортной задачи
Утверждение. Ранг системы ограничений транспортной задачи равен
( m + n − 1). Отсюда следует, что базисное решение будет иметь ( m + n − 1)
базисную компоненту.
Для любой ЗЛП, заданной в каноническом виде, имеются три возможных результата:
1. Задача разрешима.
2. Задача неразрешима из-за неограниченности целевой функции.
3. Задача несовместна.
Причем какая ситуация будет реализована, можно узнать только в
процессе ее решения симплекс-методом.
Однако для транспортной задачи имеет место следующая теорема.
Теорема. Для того чтобы транспортная задача была разрешима, необходимо и достаточно выполнение условия баланса (4.1).
Замечание. К задаче вида (4.1)–(4.4) могут сводиться и другие вербальные модели, возможно, не имеющие никакого отношения к перевозкам.
Однако всегда ЗЛП (4.1)–(4.4) называется транспортной задачей.
От обычной ЗЛП в канонической форме транспортная задача отличается тем, что в ней ищется минимум функции, а не максимум. Однако нет
необходимости заменять ее функцией поиска максимума, т. к. если есть поиск минимума, то процесс решения не меняется, но при этом критерием оптимальности являются неположительные оценки, т. е. Δ ij ≤ 0 .
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4.2. Решение транспортной задачи. Метод потенциалов
Транспортная задача является ЗЛП в канонической форме, поэтому
для ее решения можно применить симплекс метод.
Если матрица ограничений ЗЛП не имеет единичных столбцов, то ее
решение проводится в три этапа.
Этап 1. Построение начального базисного решения. (Симплекс-метод
с искусственным базисом.)
Этап 2. Проверка базисного решения на оптимальность. Если оптимальное, то конец. Иначе этап 3.
Этап 3. Перестроение базисного решения. Переход к этапу 2.
Симплекс-метод, используемый для решения транспортной задачи,
называется методом потенциалов.
Рассмотрим теперь основные этапы метода потенциалов применительно к транспортной задаче.
Замечание. К основным этапам симплекс-метода в методе потенциалов будет добавлен четвертый этап.
Этап 1. Построение начального базисного решения
Несмотря на то, что в матрице ограничений транспортной задачи отсутствуют единичные столбцы, начальное базисное решение может быть получено без введения искусственных переменных в соответствии со следующей
достаточно простой идеей. Выбирается произвольная клетка xij таблицы Х, и
в нее заносится максимально возможный по значению элемент. Так как каждое xij ≤ Ai и xij ≤ B j , то максимально возможное значение xij = min( Ai , B j ) .
Допустимое решение заносится в матрицу Х, в которой будет заполнено ( m + n − 1) клеток, т. к. ранг матрицы C равен ( m + n − 1 ).
При этом должны выполняться следующие условия.
1. Сумма xij по строкам равна Ai.
2. Сумма по столбцам равна Bj.
Алгоритм построения начального базисного решения
Шаг 0. k = 0.
Шаг 1. Выбирается произвольная свободная клетка (i, j).
Шаг 2. Вычисляется xij = min( Ai , B j ) .
= B j − xij .
Шаг 3. Если xij = Ai , то i-я строка вычеркивается, а B нов
j
Шаг 4. Иначе вычеркивается j-й столбец, а Aiнов = Ai − xij .
Шаг 5. k = k + 1 .
Шаг 6. Если k = m + n − 1 , то
Конец.
Иначе переход к шагу 1.
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В алгоритме построения базисного решения не задается способ выбора
клетки (i, j) для заполнения. Мы предлагаем два наиболее распространенных
метода заполнения клеток при построении начального базисного решения.
1. Метод северо-западного угла. (В этом случае для заполнения выбирается левая верхняя клетка.)
2. В методе северо-западного угла не учитывается стоимость перевозок, вследствие чего полученное базисное решение может быть далеким от
оптимального. Поэтому при заполнении клеток можно предложить в первую очередь заполнять клетки с наименьшей стоимостью перевозок. Этот
метод называется методом минимального элемента.
Пример 4.1. Имеется транспортная задача (рис. 4.3).
5
3
2
1
8
Bj
4
6
4
2
10
3
2
5
3
7
1
4
3
4
11
2
3
1
5
9
7
8
10
20
Аi
Рис. 4.3
1. Используем при выборе клеток для заполнения метод северозападного угла (рис. 4.4).
7
7
1
7
3
7
8
1
10
7
0 11 9 20 9
8
10
7 11 9
1
3
0
Рис. 4.4
Невычеркнутых элементов осталось 8, т. к. ранг матрицы равен 8, т. е.
матица размера 5 × 4. 5 + 4 – 1 = 8 (m + n – 1).
С ( x) = 5 ⋅ 7 + 3 ⋅ 1 + 6 ⋅ 7 + 4 ⋅ 3 + 5 ⋅ 7 + 3 ⋅ 0 + 4 ⋅ 11 + 5 ⋅ 9 = 216 .
2. Метод минимального элемента (рис. 4.5).
7
7
7
8
8
10
10
2
1
1
2
7
11
4
3
Рис. 4.5
46
9
9
8
10
20
1
1
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
С ( x) = 7 ⋅ 1 + 1 ⋅ 4 + 7 ⋅ 2 + 1 ⋅ 3 + 9 ⋅ 1 + 8 ⋅ 1 + 1 ⋅ 2 + 2 ⋅ 4 = 73 .
Видно, что значение целевой функции на допустимом решении, полученном с помощью метода минимального элемента, лучше по сравнению
с другими вариантами. То есть метод минимального элемента – хороший
способ нахождения субоптимального решения (решения, близкого к оптимальному).
Однако поскольку этот метод является эвристическим, не следует надеяться, что с его помощью всегда будет получено хорошее решение.
?
??
Задания для самостоятельной работы
1. Придумать пример транспортной задачи, при решении которой использование метода минимального элемента даст допустимое
решение со значением целевой функции, большим, чем при решении
той же задачи с использованием метода северо-западного угла.
2. Придумать собственный подход к выбору клеток для заполнения и обосновать его целесообразность.
Замечание. При построении начального базисного решения на каждом шаге вычеркивается либо строка, либо столбец, а на последнем шаге
остается не вычеркнутой и заполняется ровно одна клетка, таким образом,
общее количество заполненных клеток (m + n – 1). Так как число базисных
компонент в транспортной задаче равно (m + n – 1), то можно предположить, что мы получили базисное решение.
Этап 2. Вычисление оценок и проверка решения на оптимальность
Наша задача ориентирована на min, поэтому нужно учесть критерий
оптимальности Δ ij ≤ 0 .
Оценки можно вычислять, используя двойственную задачу, а именно
выписываются ограничения двойственной задачи, базисные ограничения
записываются как равенства, и из полученной системы находится псевдорешение двойственной задачи. Найденные значения двойственных переменных подставляются в небазисные ограничения двойственной задачи, в
которых правые части перенесены влево со знаком «минус». Полученные
значения и есть оценки.
Переходим к вычислению оценок для транспортной задачи. Выпишем
задачу, двойственную к транспортной. Обозначим через U i двойственные
переменные к первому блоку ограничений транспортной задачи и через V j –
ко второму блоку ограничений:
Ui
n
∑x
j =1
ij
= Ai , где i = 1, m ,
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Vj
m
∑x
i =1
ij
= B j , где j = 1, n ,
xij ≥ 0 .
∑c
ij
xij → min .
Двойственное ограничение при переменной xij будет следующим:
xij
U i + V j ≤ Cij ,
а целевая функция
m
n
i =1
j =1
g (U ,V ) = ∑U i Ai + ∑Vi B j → max .
Двойственные переменные могут быть как положительными, так и
отрицательными, т. к. транспортная задача записана в канонической форме.
Обозначим через B множество (i, j ) пар индексов базисных переменных
xij . Следуя теории симплекс-метода, двойственное ограничение, соответствующее (i, j ) ∈ B , запишем как равенство
xij U i + V j = Cij , (i, j ) ∈ B .
Из этой системы найдем U i , V j .
Так как количество ограничений равно (m + n – 1), а количество переменных равно (m + n), будем полагать, что всегда U1 = 0 и тогда
U i = Cij − V j ,
V j = Cij − U i .
Вычисляем для всех небазисных (i, j ) ∉ B оценки Δ ij по формуле
Δ ij = U i + V j − Cij .
Алгоритм выполнения этапа 2
Шаг 1. Для всех (i, j ) ∈ B записывается уравнение U i + V j = Ci . j .
Шаг 2. U1 = 0.
Шаг 3. Вычисление остальных потенциалов U i , V j по формулам:
U i = C ij − V j ,
V j = Cij − U i .
Шаг 4. Для всех (i, j ) ∉ B вычисляются оценки Δ ij :
Δ ij = U i + V j − Cij .
Шаг 5. Если все Δ ij ≤ 0 , то переход к этапу 4.
Иначе переход к этапу 3.
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Этап 3. Перестроение базисного решения
Пусть существует Δ i j > 0 . Как следует из теории симплекс-метода,
0 0
если переменную xi j сделать базисной, то значение целевой функции
уменьшится.
Посмотрим, как получить значение xi j = θ при отсутствии обычной
симплекс-таблицы. Так как сумма элементов в каждой строке и в каждом
столбце в матрице допустимого решения Х должна сохраняться, то если какой-то элемент строки увеличивается, очевидно, что значение некоторого
другого элемента в этой же строке должно быть уменьшено, а некоторое
значение в столбце, в котором значение элемента уменьшено, должно быть
увеличено и т. д.
Поскольку в строке матрицы может быть несколько ненулевых элементов, то при увеличении одного из них не всегда понятно, какой именно
нужно уменьшить. То же самое относится и к столбцу.
Эти элементы можно определить с помощью правила вычеркивания.
0 0
0 0
Правило вычеркивания
Пусть задана транспортная таблица, в которой выделены некоторые
элементы. Просматриваются строки, и вычеркиваются те, которые содержат
не более одного выделенного элемента. Затем просматриваются столбцы, и
вычеркиваются те, которые содержат не более одного выделенного элемента и т.д. Процесс вычеркивания завершается в двух случаях:
1. Все элементы вычеркнуты.
2. В каждой из невычеркнутых строк и столбцов содержатся не менее
двух выделенных элементов.
Имеют место следующие утверждения.
Утверждение 1. Столбцы Pij , соответствующие вычеркнутым элементам, линейно независимы.
Утверждение 2. Допустимое решение транспортной задачи, построенное с помощью метода северо-западного угла или метода минимального
элемента, является базисным.
Алгоритм перестроения базисного решения
Шаг 1. Выбираем Δ i j > 0 .
Шаг 2. Полагаем xi j = θ .
Шаг 3. К транспортной таблице, со всеми выделенными базисными
xij и добавленными к ним θ , применяется правило вычеркивания. Оставшиеся невычеркнутыми элементы образуют цикл.
Шаг 4. При движении по циклу от θ расставляются знаки «минус» и
«плюс» поочередно.
0 0
0 0
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 5. Полагаем θ = min xij− .
Шаг 6. Перестраивается базисное решение по формулам
xi j = θ ,
xij− нов = xij− − θ ,
xij+ нов = xij+ + θ ,
xijнов = xij
для невычеркнутых элементов.
Шаг 7. Один из элементов, помеченный знаком «минус», который после преобразования стал или был равным нулю, исключается из базиса.
Шаг 8. Переход к этапу 1.
Замечание. Если после преобразования образовалось два или несколько xij = 0 , то можно убрать любой из этих элементов, однако т. к. мы
ищем минимальное значение целевой функции, исключить можно тот элемент, которому соответствует большее значение сij .
0 0
Этап 4. Вычисление оптимального значения целевых функций
двойственной пары
В соответствии с теорией двойственности на оптимальных решениях
значения целевой функции исходной и двойственной задач совпадают, поэтому на третьем этапе вычисляются значения целевой функции исходной и
двойственной задач и проверяется их равенство.
Алгоритм выполнения этапа 4
Шаг 1. Выписать последнюю транспортную таблицу.
Шаг 2. Над сформированной таблицей пишутся следующие слова:
*
« x – оптимальное решение».
Шаг 3. В транспортную таблицу добавляются cij : (i, j ) ∈ B , а также
справа от таблицы записываются Ai , а снизу – B j .
Шаг 4. Вычисляется оптимальное значение исходной целевой функции
c( x * ) = ∑ сij xij* .
( i , j )∈B
Шаг 5. Вычисляется значение двойственной целевой функции
m
n
i =1
j =1
g (U * ,V * ) = ∑U i* Ai + ∑V j* B j .
Шаг 6. Проверяется выполнение равенства c( x * ) = g (U * ,V * ) .
Шаг 7. Конец.
Пример 4.2. Имеем транспортную задачу (рис. 4.6).
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5
3
2
1
8
Bj
4
6
4
2
10
3
2
5
3
7
1
4
3
4
11
Ai
2
3
1
5
9
7
8
10
20
Рис. 4.6
Матрица Х – начальное базисное решение, найденное с помощью
произвольного выбора xij (рис. 4.7).
Ai
7
7
7
(1)
(2)
8(4)
10
10
4
11
4
(6)
Bj
8
(3)
8
1
2
(5)
10
2
20
10
6
9
8
6
(7)
7
1
(8)
6
Рис. 4.7
Вычислим потенциалы:
U3 + V5 = 1,
U1 + V4 =1,
U2 + V3 = 2,
U4 + V2 = 2,
U2 + V5 = 3,
U4 + V4 = 4,
U3 + V1 = 2,
U4 + V5 = 5,
U1 = 0,
U2 = 1,
U3 = –1,
U4 = 3,
Занесем полученные результаты в таблицу (рис. 4.8).
Vj
Ui
0
1
–1
3
3
–1
1
1
V1 = 3,
V2 = –1,
V3 = 1,
V4 = 1,
V5 = 2.
2
7
7
8
10
4
1
2
6
Рис. 4.8
Для небазисных мест Δ ij = U i + V j − Cij (вычисление оценок и проверка
на оптимальность) (рис. 4.9)
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Vj
3
Ui
–1
1
1
2
0
–2
–5
–2
7
0
1
1
–6
7
6
1
–1
8
–6
–5
–3
2
3
5
10
1
4
6
Рис. 4.9
Для введения в базис выбираем клетку (4;1), т. к. Δ 4;1 = 5 > 0 (решение неоптимальное), и поставим x4;1 = θ .
Определяем цикл, связывающий θ с базисными элементами, по правилу вычеркивания.
−
Расставим знаки при элементах цикла. θ = min xij = 6 (рис. 4.10).
(1)
7
7
8–
θ
(5)
1
2+
10
(2)
4
(3)
6–
(4)
Рис. 4.10
Продолжаем перестраивать базисное решение (рис. 4.11–4.14).
Vj
Ui
0
6
4
3
–2
–7
1
2–
6+
–1
–4
–5
–1
–1
10
–7
7
Рис. 4.11
52
–5
–4
1
7
3
2
4–
–3
–5
1–
8+
–5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7
θ
7
1–
2–
8+
6+
4-
10
θ =1
Рис. 4.12
Vj
–2
Ui
–1
–1
0
–7
–5
3
–2
–4
4
1–
3
7+
1
–4
7
–1
–3
7
–5
1
–3
–2
–1
10
2
θ
3–
9
–5
Рис. 4.13
7
7
1
θ
17+
9
3-
10
θ =1
Рис. 4.14
Новое базисное решение и новые оценки представлены на рис. 4.15.
Vj
Ui
–2
–1
–1
0
–7
–5
3
–2
–4
2
–2
–3
3
8
10
Рис. 4.15
53
1
–4
7
–1
7
–3
1
–1
–4
1
–1
2
9
–3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Выписываем новую таблицу.
x * – оптимальное решение
Vj
Ui
–2
–1
–1
0
7(2)
3
1
3
8(1)
10(2)
Bi
8
10
7
1(4)
8
9(1)
2(4)
7
Ai
7(1)
1(3)
2
–1
11
10
20
9
Все оценки Δ ij < 0 , значит решение оптимальное.
Вычисляем оптимальное значение исходной целевой функции:
С(х*) = 7 ⋅ 1 + 1 ⋅ 4 + 7 ⋅ 2 + 1 ⋅ 3 + 9 ⋅ 1 + 8 ⋅ 1 + 1 ⋅ 2 + 2 ⋅ 4 = 73 .
Вычисляется оптимальное значение двойственной целевой функции:
G(U*,V) = 0 ⋅ 7 + 3 ⋅ 8 + 2 ⋅ 10 + 3 ⋅ 20 − 2 ⋅ 8 − 1 ⋅ 10 − 1 ⋅ 7 + 1 ⋅ 11 − 1 × 9 = 73 .
c( x * ) = g (U * ,V * ) .
?
??
Задание для самостоятельной работы
Убедитесь в том, что из алгоритма метода потенциалов вытекает следующее утверждение:
Если в транспортной задаче все Ai и B j являются целыми
числами, то любое допустимое базисное решение также целое.
4.3. Транспортные задачи, имеющие усложнения в постановке
Транспортная задача с запретами
(в транспортной задаче запрещены некоторые маршруты перевозок)
Довольно часто в транспортных задачах может оказаться, что между
некоторыми поставщиками и потребителями отсутствуют коммуникации.
Обозначим через Ji множество номеров потребителей, которые связаны коммуникациями с i-м поставщиком со стоимостью перевозок сij , а через Ii – множество номеров поставщиков, которые связаны коммуникациями с j-м потребителем со стоимостью перевозок сij , тогда математическая
модель примет вид
∑ xij = Ai , i = 1, m ,
j∈J i
54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
∑x
i∈I j
ij
= B j , j = 1, n ,
xij ≥ 0 ,
∑ ∑ xij сij → min .
i∈I j j∈J i
Заметим, что в этом случае даже при выполнении условия баланса задача может оказаться несовместной.
Такая задача после некоторых преобразований сводится к обычной
транспортной задаче.
Полагаем сij = М (М – большое число), где i ∉ I j и j ∉ J i , полученная
задача решается методом потенциалов.
Если в оптимальном решении xij > 0 , там, где сij =М,то исходная задача несовместна.
Если при всех сij = М все xij = 0 , то найдено решение исходной задачи.
Несбалансированные транспортные задачи
Рассмотрим случай, когда в транспортной задаче условие баланса не
выполнено, т. е. суммарное наличие продукции больше суммарной потребности либо, наоборот, спрос превышает предложение.
Так как условие баланса является необходимым и достаточным для
существования решения транспортной задачи, то несбалансированную задачу необходимо свести к сбалансированной.
Рассмотрим оба случая:
1. Пусть
m
n
i =1
j =1
∑ Ai > ∑ B j , т. е. предложение превышает спрос.
В этом случае, очевидно, не вся продукция от поставщиков будет отправлена потребителям, поэтому математическая модель примет вид
n
∑x
j =1
ij
≤ Ai , i = 1, m ,
ij
= B j , j = 1, n ,
m
∑x
i =1
xij ≥ 0 ,
m
n
∑∑ x с
i =1 j =1
2. Пусть
m
n
i =1
j =1
ij
ij
→ min .
∑ Ai < ∑ B j , т. е. спрос превышает предложение.
Математическая модель:
n
∑x
j =1
ij
= Ai , i = 1, m ,
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
m
∑x
i =1
≤ B j , j = 1, n ,
ij
xij ≥ 0 ,
m
n
∑∑ x с
ij
i =1 j =1
ij
→ min .
Рассмотрим способ сведения несбалансированных задач 1 и 2 к сбалансированным.
Для случая 1 введем дополнительную переменную xi ( n+1) – количество
продукции, которая осталась на складе i-го поставщика, т. е. не вывезенная
к потребителям продукция. Получим
n
∑x
j =1
ij
m
∑x
i =1
m
∑x
i =1
i ( n +1)
+ xi ( n +1) = Ai ,
= B j , j = 1, n ,
ij
m
n
i =1
j =1
= ∑ Ai − ∑ B j = B( n +1)
ci ( n+1) = 0
или
n +1
∑x
j =1
m
∑x
i =1
ij
m
ij
= Ai , i = 1, m ,
≤ B j , j = 1, (n + 1) ,
n
∑∑ x с
ij
i =1 j =1
ij
→ min .
Таким образом, к таблице исходных данных надо добавить (n + 1) -й
столбец с целевыми коэффициентами, равными нулю, и
m
n
i =1
j =1
B( n+1) = ∑ Ai − ∑ B j .
Для случая 2 введем дополнительную переменную x( m+1) j – количество
продукции, которое недодали j-му потребителю.
m
∑x
i =1
+ x( m +1) j = B j , j = 1, n ,
ij
n
∑x
j =1
ij
= Ai , i = 1, m ,
n
n
m
j =1
j =1
i =1
∑ x( m+1) j = ∑ B j − ∑ Ai = A( m+1)
c( m +1) j = 0
или
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
m +1
∑x
i =1
n
∑x
j =1
ij
m
= B j , j = 1, n ,
ij
= Ai , i = 1, (m + 1) ,
n
∑∑ x с
ij
i =1 j =1
ij
→ min .
К таблице исходных данных добавляется (m + 1) строка с целевыми
n
m
j =1
i =1
коэффициентами, равными нулю, и A( m +1) = ∑ B j − ∑ Ai .
Далее решается сбалансированная транспортная задача с помощью
метода потенциалов. После решения добавленный столбец или строка отбрасываются.
Замечание. Если в транспортной задаче с добавленной строкой либо
столбцом начальное базисное решение ищется методом минимального элемента, то рекомендуется искать минимальные элементы исходной матрицы С.
Пример 4.2. Пусть задана следующая транспортная задача (рис. 4.16).
Bj
5
3
2
1
12
4
6
4
2
9
3
2
5
3
8
1
4
3
4
5
Ai
20
8
7
10
2
3
1
5
6
Рис. 4.16
Задача несбалансированна, т. к.
4
∑A
i =1
i
5
= 45 > ∑ B j = 40 . Поэтому необj =1
ходимо добавить столбец с целевыми коэффициентами, равными нулю, и
B6 = 45 − 40 = 5 (рис. 4.17).
Ai
Bj
5
3
2
1
4
6
4
2
3
2
5
3
1
4
3
4
2
3
1
5
0
0
0
0
12
9
8
5
6
5
Рис. 4.17
Задача решается методом потенциалов (рис. 4.18).
57
20
8
7
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Vj
3
Ui
0
–1
–1
–2
–2
–1
2
10
4
3
1
2
0
9
–3
–1
0
0
8
–3
–2
5
1
–2
5
–5
5
–4
–3
–5
–1
–1
–2
Рис. 4.18
Окончательный вид оптимального решения после исключения последнего столбца следующий (рис. 4.19).
Ai
9
0
5
1
8
2
8
5
7
10
Bj
12
20
10
9
8
5
6
Рис. 4.19
Из рис. 4.19 видим, что у первого поставщика осталось пять единиц
невывезенной продукции.
Вычисляем значение целевой функции:
C(x) = 9 ⋅ 4 + 0 ⋅ 3 + 5 ⋅1 + 1⋅ 2 + 8 ⋅ 2 + 2 ⋅ 2 + 5 ⋅1 + 10 ⋅1 = 78 .
Вычисляется оптимальное значение двойственной целевой функции:
g (U * ,V * ) = 78 . c( x * ) = g (U * ,V * ) .
Пример 4.3. Имеем несбалансированную транспортную задачу (рис. 4.20).
Ai
Bj
5
4
3
1
2
20
3
6
2
4
3
8
2
4
5
3
1
7
1
2
3
4
5
10
12
15
10
8
5
Рис. 4.20
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4
5
i =1
j =1
∑ Ai = 45 < ∑ B j = 50 . Добавляем
Задача несбалансированна, т. к.
строку с целевыми коэффициентами, равными нулю, и A5 = 50 − 45 = 5 . Получаем следующую задачу (рис. 4.21).
Ai
Bj
5
4
3
1
2
20
3
6
2
4
3
8
2
4
5
3
1
7
1
2
3
4
5
10
0
0
0
0
0
5
12
15
10
8
5
Рис. 4.21
Задача решается методом потенциалов (рис. 4.22).
Vj
3
Ui
0
–1
–1
–2
–3
–
–
4
3
1
2
10
2
8
8
0
–
–
0
2
10
0
5
–
–
0
–
–
–
–
–
5
–
–
Рис. 4.22
Так как все оценки отрицательны, то решение оптимально. Окончательный вид оптимального решения после исключения последней строки
следующий (рис. 4.23).
Ai
10
Bj
2
10
12
2
8
8
0
5
15
10
Рис. 4.23
59
8
5
20
8
7
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Потребность второго потребителя не удовлетворена на пять единиц.
Оптимальное значение целевой функции
C(x)=10 ⋅ 4 + 2 ⋅ 3 + 8 ⋅1 + 0 ⋅ 2 + 8 ⋅ 2 + 2 ⋅ 2 + 5 ⋅1 + 10 ⋅1 = 89 .
Вычисляется оптимальное значение двойственной целевой функции:
g (U * ,V * ) = 89 .
c( x * ) = g (U * ,V * ) .
Лабораторная работа № 6
Даны матрица С размером (4 × 5), количество продуктов i-го поставщика Аi и потребность потребителя B j (рис. 4.24).
Аi
Вj
5
3
2
1
4
6
4
2
3
2
5
3
1
4
3
4
2
3
1
5
Рис. 4.24
Составить план перевозки продукции от поставщиков к потребителям
так, чтобы суммарные затраты на перевозку были минимальными, для чего
выполнить следующие задания.
1. Сбалансировать задачу.
2. Найти начальное допустимое решение методом:
а) северо-западного угла,
б) минимального элемента.
3. Допустимое решение, найденное методом минимального элемента,
проверить на оптимальность.
4. Если решение в (3) неоптимальное, то найти оптимальное решение
с помощью метода потенциалов.
5. Если в (3) доказана оптимальность, то найти оптимальное решение
методом потенциалов, начиная с допустимого решения, найденного методом северо-западного угла.
6. Для оптимального решения найти значения целевых функций исходной и двойственной задач.
Значения Ai и B j для различных вариантов приведены в табл. 4.1
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таблица 4.1
Номер
варианта
A1
A2
A3
A4
B1
B2
B3
B4
B5
1
15
9
7
11
12
8
10
9
6
2
16
8
8
10
15
9
7
6
8
3
21
13
12
9
14
11
10
8
7
4
20
10
8
13
13
10
7
9
8
5
18
12
10
12
16
13
9
8
10
6
19
11
9
10
17
12
10
8
7
7
17
8
16
15
15
10
13
9
12
8
22
10
11
9
18
11
12
8
7
9
14
8
7
13
9
10
6
7
8
10
17
10
11
16
14
9
13
6
10
11
11
9
15
7
12
8
10
9
6
12
8
16
8
10
15
9
6
7
8
13
21
12
13
9
11
14
10
8
7
14
10
8
20
13
13
10
9
7
8
15
18
12
10
12
13
10
9
8
16
16
11
19
9
10
17
10
12
8
7
17
17
8
15
16
10
15
12
9
13
18
11
10
9
22
18
11
12
8
7
19
14
7
8
13
9
10
7
6
8
20
16
11
10
17
14
9
10
6
13
21
15
9
7
11
12
10
8
9
6
22
16
8
8
10
15
7
9
6
8
23
13
21
12
9
14
11
10
8
7
24
10
20
8
13
13
10
7
9
8
25
10
12
18
12
16
13
9
8
10
26
10
11
9
19
17
12
10
8
7
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Список литературы
1. Азарнова Т. В. Методы оптимизации. Элементы теории, алгоритмы и
примеры / Т.В. Азарнова, И.Л. Каширина, Г.Д. Чернышова. – Воронеж : Воронеж. гос. ун-т, 2004. – 151 с.
2. Аснина А. Я. Оптимизационные задачи в экономике : практикум /
А.Я. Аснина Н. Г. Аснина, О. С. Нильга ; Воронеж гос. арх.-строит. ун-т. –
Воронеж, 2009. – 68 с.
3. Ашманов С. А. Линейное программирование / С. А. Ашманов. – М. :
Наука, 1981. – 304 с.
4. Банди Б. Основы линейного программирования / Б. Банди. – М. : Радио
и связь, 1989. – 176 с.
5. Исследование операций в экономике : учеб. пособие для вузов /
Н. Ш. Кремер [и др.] ; под ред. Н. Ш. Кремера. – М. : Юнити, 2004. – 407 с.
6. Красс М. С. Основы математики и ее приложения в экономическом
образовании : учебник / М. С. Красс, Б. П. Чупрынов. – 2-е изд., испр. – М. :
Дело, 2001. – 688 с.
7. Таха Хемеди А. Введение в исследование операций : пер. с англ. /
Хемеди А. Таха. – 7-е изд. – М. : Вильямс, 2005. – 912 с.
62
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Учебное пособие
Составители:
Аснина Альбина Яковлевна,
Аснина Наталия Георгиевна
Редактор А. Ю. Котлярова
Подп. в печ. 04.07.2011. Формат 60×84/16.
Усл. печ. л. 3,7. Тираж 50 экз. Заказ 424.
Издательско-полиграфический центр
Воронежского государственного университета.
394000, г. Воронеж, пл. им. Ленина, 10. Тел. (факс): +7 (473) 259-80-26
http://www.ppc.vsu.ru; e-mail: pp_center@ppc.vsu.ru
Отпечатано в типографии
Издательско-полиграфического центра
Воронежского государственного университета.
394000, г. Воронеж, ул. Пушкинская, 3. Тел. +7 (473) 220-41-33
63
Документ
Категория
Физико-математические науки
Просмотров
175
Размер файла
761 Кб
Теги
линейной, программирование, 151
1/--страниц
Пожаловаться на содержимое документа