Файл: Учебнометодическое пособие по дисциплине Логистика производства для инженеров техники и технологий по специальности 230104 Системы автоматизированного проектирования.pdf

67 ограничений). Такие методы позволяют решать частные задачи анализа на чувствительность.
Двойственность. Представить в общем виде приемы и методы анализа на чувствительность в теории линейного программирования позволяет понятие двойственности.
Рассмотрим формулировку двойственной задачи, соответствующей задаче, представленной соотношениями (3.1) – (3.3).
Целевая функция имеет вид:
Минимизировать
Σ b
i
y
i
=> min, (3.4) где i = 1, m; j = 1, n.
Система ограничений задана в виде совокупности неравенств:
Σ a
ij
y
i
> c
j
, (3.5)
Все переменные принимают только неотрицательные значения:
y
i
> 0. (3.6)
В качестве иллюстрации рассмотрим задачу, двойственную к тому примеру, который был приведен. Минимизировать целевую функцию:
15 y
1
+ 120 y
2
+ 100 y
3
=> min
При ограничениях, заданных системой неравенств:
1 y
1
+ 7 y
2
+ 3 y
3
> 4 1 y
1
+ 5 y
2
+ 5 y
3
> 5,
1 y
1
+ 3 y
2
+ 10 y
3
> 9,
1 y
1
+ 2 y
2
+ 15 y
3
> 11,
y
1
> 0, y
2
> 0, y
3
> 0.
Матрица ограничений двойственной задачи транспонирована по отношению к матрице ограничений исходной (прямой) задачи. Знаки неравенств двойственной задачи противоположны знакам неравенств прямой задачи.
Константы ограничений исходной модели совпадают с коэффициентами целевой функции двойственной модели. Константы ограничений двойственной модели совпадают с коэффициентами целевой функции исходной модели. Исходная и двойственная задачи дополняют друг друга до определенной целостности, как и в других видах двойственности.
Теорема двойственности утверждает, что: если исходная и двойственная задачи имеют допустимые решения, то существуют оптимальные решения для обеих задач и значения целевых функций для этих оптимальных решений совпадают. Если одна из задач допускает оптимальное решение, для которого значение целевой функции ограничено, то соответствующая двойственная задача допускает оптимальное решение при том же значении целевой функции.
Следствием теоремы двойственности является теорема о дополнительной
нежесткости, которая формулируется следующим образом.
PDF created with pdfFactory Pro trial version www.pdffactory.com

68
Пусть x*
j
(j = 1, 2, …, n) – решение исходной задачи, а y*
i
(i = 1, 2, …, m) – решение соответствующей двойственной задачи. Оба решения являются оптимальными тогда, и только тогда, когда
y*
i
(
Σ a
ij
x*
j
– b
i
) = 0; (i = 1, 2, …, m),
x*
j
(
Σ a
ij
y*
i
– c
j
) = 0; (j = 1, 2, …, n).
Отсюда вытекает, что всякий раз, когда модель содержит ограничение в виде строгого неравенства, соответствующая переменная в двойственной задаче принимает нулевое значение.
Современные пакеты прикладных программ позволяют пользователю решать задачи оптимизации перевозок путем задания условий и нажимания соответствующих кнопок. Вместе с тем для осознанного участия в организации логистической системы и управлении ею полезно, а порой необходимо знать и понимать механизмы работы методов и алгоритмов решения таких задач.
Решение примера. Рассмотрим применение симплекс-метода для решения связанной с логистикой задачи линейного программирования, пример которой был представлен выше. Обозначим через x
0
значение целевой функции и введем в каждое ограничение свободную переменную, соответственно, x
5
, x
6
, x
7
, что позволит привести неравенства к равенствам.
1 x
0
– 4 x
1
– 5 x
2
– 9 x
3
– 11 x
4
= 0 строка 0
При ограничениях, приведенных к равенствам:
1 x
1
+ 1 x
2
+ 1 x
3
+ 1 x
4
+ 1 x
5
= 15 строка 1
7 x
1
+ 5 x
2
+ 3 x
3
+ 2 x
4
+ 1 x
6
= 120 строка 2
3 x
1
+ 5 x
2
+ 10 x
3
+ 15 x
4
+ 1 x
7
= 100 строка 3
Все переменные неотрицательные: x
1
, x
2
, x
3
, x
4
, x
5
, x
6
, x
7
> 0.
Выполним шаги алгоритма симплекс-метода с использованием двух симплекс-критериев, которые рассмотрены выше.
Начнем с итерации 1.
Шаг 1. Из множества возможных начальных допустимых решений выберем удобное пробное решение: x
0
= 0, x
5
= 15, x
6
= 120, x
7
= 100, а остальные переменные пусть равны нулю. Это исходное базисное решение.
Таким образом, исходная прибыль равна нулю, x
0
= 0.
Шаг 2. Применим критерий 1. Если ли в строке 0 есть небазисные переменные, коэффициенты при которых меньше нуля, то выбираем среди них переменную с наибольшим абсолютным значением стоящего перед ней коэффициента (он обеспечивает наибольшее удельное приращение целевой функции). Вводим эту переменную в очередной базис. Анализ коэффициентов в целевой функции показывает, что следует ввести в базис переменную x
4
с наибольшим коэффициентом перед ней, равным 11. Увеличение этой переменной на 1 приводит к возрастанию целевой функции на 11. Теперь надо определить, какую переменную выводить из базиса.
PDF created with pdfFactory Pro trial version www.pdffactory.com

69
Шаг 3. Применим критерий 2. Отношения ограничений в правых частях к коэффициентам при новой базисной переменной x
4
равны по строкам:
b
1
/ a
14
= 15/ 1 = 15 строка 1,
b
2
/ a
24
= 120 / 2 = 60 строка 2,
b
3
/ a
34
= 100 / 15 = 6,67 строка 3.
Наименьшее значение отношения получено в строке 3; именно к этому значению, согласно критерию 2, приравниваем новую переменную: x
4
= 6,67. А прежнюю базисную переменную в этой строке надо из базиса вывести; это возможно за счет уменьшения значения переменной x
7
до нуля.
Шаг 4. Преобразуем исходные уравнения так, чтобы в строке 3 коэффициент при x
4
был равен 1, а в строках 0, 1, 2 – нулю. Такое преобразование называют операцией замены базиса, или операцией замены
опорного плана. Для этого будем умножать обе части уравнений на одно и то же число, а затем складывать строки таким образом, чтобы достичь желаемого результата. Это законные операции с точки зрения математики, поскольку выполняем действия умножения равных величин на одно и то же число и сложение равных друг другу левых и правых частей.
Сначала разделим обе части уравнения в строке 3 на коэффициент при x
4
, т.е. на 15, получим:
1/5 x
1
+ 1/3 x
2
+ 2/3 x
3
+ 1 x
4
+ 1 /15x
7
= 3/20 строка 3.
Коэффициент при x
4
принял здесь значение, равное единице. Теперь обратим в нули коэффициенты при x
4
в остальных уравнениях. Для этого выполним следующие действия:
Умножим строку 3 на 11 и результат прибавим к строке 0;
Умножим строку 3 на –1 и результат прибавим к строке 1;
Умножим строку 3 на –2 и результат прибавим к строке 2.
В результате получим следующие уравнения.
1 x
0
– 9/5 x
1
– 4/3 x
2
– 5/3 x
3
+ 11/15 x
7
= 220/3 строка 0,
4/5 x
1
+ 2/3 x
2
+ 1/3 x
3
+ 1 x
5
– 1/15 x
7
= 25/3 строка 1,
33/5 x
1
+ 13/3 x
2
+ 5/3 x
3
+ 1 x
6
– 2/15 x
7
= 320/3 строка 2.
Строка 3 уже получена выше. В силу законности выполненных операций можно утверждать, что данная система уравнений эквивалентна исходной системе уравнений, хотя внешне на нее и не похожа.
Представление системы уравнений в таком виде удобно потому, что, полагая небазисные переменные равными нулю, т.е. x
1
= x
2
= x
3
= x
7
= 0, можно сразу определить значения переменных для нового базисного решения. Они равны: x
0
= 220/3, x
4
= 20/3, x
5
= 25/3, x
6
= 320/3.
Прибыль в новом базисе стала равна, как можно видеть, x
0
= 220/3.
Численное значение прибыли на новой итерации t, т.е. x
0
(t), можно определить по значению прибыли на предыдущей итерации (t - 1), т.е. x
0
(t - 1) и удельному
PDF created with pdfFactory Pro trial version www.pdffactory.com

70 вкладу новой базисной переменной x
k
в приращение прибыли c
k
(max) (b
i
/ a
ik
)
потакой формуле:
x
0
(t) = x
0
(t - 1) + c
k
(max) (b
i
/ a
ik
)
В нашем примере получим, что
x
0
(1) = x
0
(0) + c
k
* (b
3
/ a
34
) = 0 + 11 * (100/15) = 220/3.
Напомним, что исходная прибыль была равна нулю. Выполненные действия проясняют смысл критерия 2. Если из пробного базиса исключить не
x
7
, а x
5
, или x
6
, то x
4
, x
7
, и x
6
(или x
5
), приняли бы отрицательные значения, а это противоречит предположению, что они не отрицательные. Это легко проверить.
Выполним итерацию 2.
Возвращаемся к шагу 2, чтобы проверить – достигнуто ли оптимальное решение задачи? Применяя критерий 1, видим, что оптимальное решение не достигнуто, поскольку в строке 0 есть отрицательные коэффициенты. Таким образом, можно улучшить решение, включая в новый базис x
1
, x
2
или x
3
. Среди них наибольшее абсолютное значение, равное 9/5, имеет коэффициент при x
1
Эта переменная обеспечит наибольшее приращение целевой функции, ее и включаем в новый базис.
Далее производим расчеты для шага 3, используя критерий 2.
Отношения ограничений в правых частях к коэффициентам при новой базисной переменной x
1
равны по строкам:
b
1
/ a
11
= (25/3) / (4/5) = 125/12 = 10,42 строка 1,
b
2
/ a
21
= (320/3) / (33/5) = 1600/99 = 16,16 строка 2,
b
3
/ a
31
= (20/3) / (1/5) = 100/3 = 33,33 строка 3.
Наименьшее значение отношения получено в строке 1; поэтому в очередном пробном решении прежнюю базисную переменную x
5
заменим на переменную x
1
.С учетом проведенной замены преобразуем систему уравнений.
Как и в предыдущей итерации, сначала выполним нормировку коэффициента при x
1
в строке 1.
1 x
1
+ 5/6 x
2
+ 5/12 x
3
+ 5/4 x
5
– 1/12 x
7
= 125/12 строка 1.
Коэффициент при x
1
принял здесь значение, равное единице. Теперь обратим в нули коэффициенты при x
1
в остальных уравнениях. Для этого надо:
Умножить строку 1 на 9/5 и результат сложить со строкой 0;
Умножить строку 1 на –33/5 и результат сложить со строкой 2;
Умножить строку 1 на –1/5 и результат сложить со строкой 3.
В результате получим.
1 x
0
+ 1/6 x
2
– 11/12 x
3
+ 9/4 x
5
…….. + 7/12 x
7
= 1105/12 строка 0,
– 7/6 x
2
– 13/12 x
3
– 33/4 x
5
+ 1 x
6
+ 5/12 x
7
= 45512 строка 2,
1/6 x
2
+ 7/12 x
3
+ 1 x
4
– 1/4 x
5
+ 1/12 x
7
= 55/12 строка 3.
PDF created with pdfFactory Pro trial version www.pdffactory.com

71
Строка 1 уже получена выше. Как и раньше, можно сразу определить значения переменных для нового базисного решения: x
0
= 1105/12, x
1
= 125/12,
x
6
= 45512, x
4
= 55/12.
Выполним итерацию 3.
Возвращаемся к шагу 2, чтобы проверить – достигнуто ли оптимальное решение задачи? Применяя критерий 1, видим, что оптимальное решение не достигнуто, поскольку в строке 0 остался отрицательный коэффициент при x
3
, имеющий абсолютное значение, равное 11/12. За счет нее и может быть улучшено решение задачи. Эту переменную x
3
и включаем в новый базис.
Далее производим расчеты для шага 3, используя критерий 2.
Отношения ограничений в правых частях к коэффициентам при новой базисной переменной x
1
равны по строкам:
b
1
/ a
13
= (125/12) / (5/12) = 125/5 = 25,00 строка 1,
b
2
/ a
23
= (455/12) / (13/12) = 1600/99 = 16,16 строка 2,
b
3
/ a
33
= (55/12) / (7/12) = 55/7 = 7,85 строка 3.
В соответствии с этими расчетами наименьшее значение отношения получено в строке 1; поэтому из числа базисных переменных исключаем x
4
, которая вошла в решение на первой итерации. Случается, что в процессе выполнения симплексного алгоритма какая-либо переменная может войти в очередное пробное решение, а при следующих итерациях оказаться исключенной из базиса. По этой причине трудно определить максимальное число итераций, приводящих к оптимальному решению.
С учетом проведенной замены преобразуем систему уравнений. Как и в предыдущей итерации, сначала выполним нормировку коэффициента при x
3
в строке 1. Затем выполним преобразования системы уравнений подобно тому, как это делалось на двух предыдущих итерациях. Студенты могут проделать это в качестве домашнего задания. В результате получим следующую систему уравнений. Коэффициент при x
3
в строке 3 примет значение, равное единице.
1 x
0
+ 3/7 x
2
+ 11/7 x
4
+ 13/7 x
5
+ 5/7 x
7
= 695/7 строка 0,
1 x
1
+ 5/7 x
2
– 5/7 x
4
+ 10/7 x
5
– 1/7 x
7
= 50/7 строка 1,
– 6/7 x
2
+ 13/7 x
4
– 61/7 x
5
+ 1 x
6
+ 4/7 x
7
= 325/12 строка 2,
2/7 x
2
+ 1 x
3
+ 12/7 x
4
– 3/7 x
5
+ 1/7 x
7
= 55/7 строка 3.
Коэффициенты при x
3
в остальных уравнениях обратили в нули. В строке 0 не осталось отрицательных коэффициентов, следовательно, получено оптимальное решение, при котором целевая функция достигла максимального значения, равного 695/7 = 99,29. Это существенно больше, чем значение для начального пробного решения. Базисные переменные получили значения, соответствующие оптимальному решению: x
1
= 50/7, x
6
= 325/12, x
5
= 55/7.
Итак, это решение задачи оптимизации производства при ограничениях на ресурсы, когда получена максимальная прибыль, равная 695/7 = 99,29.
PDF created with pdfFactory Pro trial version www.pdffactory.com

72