Учебно-методическое пособие для студентов специальности 1-36 20 02 «Упаковочное производство»

7.2.3. Понятие минимизации функции 
 
Для понятия смысла минимизации целевой функции приведем 
следующий пример. Имеется некий однородный груз, который нуж-
но перевести с n складов на m заводов. Для каждого склада i извест-
но, сколько в нем находится груза a
i
, а для каждого завода известна 
его потребность b
j
в грузе. Стоимость перевозки пропорциональна 
расстоянию от склада до завода (все расстояния c
ij
от i-го склада до 
j-го завода известны). Требуется составить наиболее дешевый план 
перевозки. 
Решающими переменными в данном случае являются x
ij
– коли-
чество груза, перевезенного из i-го склада на j-й завод. Они удовле-
творяют ограничениям 
1
2
...
;
i
i
im
i
x
x
x
a

 

1
2
...
.
j
j
nj
j
x
x
x
b

 


---

34 
Целевая функция, которую надо минимизировать, имеет вид 
11 11
12 12
( )
...
.
nm nm
f x
x c
x c
x c


 
7.2.4. Игра с нулевой суммой 
Есть матрица A размера n 

m. Первый игрок выбирает число от 
1 до n, второй – от 1 до m. Затем они сверяют числа и первый игрок 
получает a
ij
очков, а второй ( –a
ij
) очков (i – число, выбранное пер-
вым игроком, j – вторым). Нужно найти оптимальную стратегию 
первого игрока. 
Пусть в оптимальной стратегии, например первого игрока, число i 
нужно выбирать с вероятностью p
i
. Тогда оптимальная стратегия яв-
ляется решением следующей задачи линейного программирования: 
0
1;
i
p


1
...
1;
n
p
p
 

1 1
2
2
...
(
1, ..., ),
i
i
ni n
a p
a p
a p
c i
m

 


в которой нужно максимизировать функцию
1
( , ... ,
, )
.
n
f p
p c
c

Значение c в оптимальном решении будет математическим ожи-
данием выигрыша первого игрока в наихудшем случае. 
Алгоритмы решения 
Наиболее известным и широко применяемым на практике для 
решения общей задачи линейного программирования (ЛП) является 
симплекс-метод. Несмотря на то, что симплекс-метод является до-
статочно эффективным алгоритмом, показавшим хорошие резуль-
таты при решении прикладных задач ЛП, он является алгоритмом с 
экспоненциальной сложностью [5, 7]. Причина этого состоит в ком-
бинаторном характере симплекс-метода, последовательно переби-

---

35 
рающего вершины многогранника допустимых решений при поиске 
оптимального решения. 
Первый полиномиальный алгоритм, метод эллипсоидов, был пред-
ложен в 1979 году советским математиком Л. Хачияном, разрешив-
шим таким образом проблему, долгое время остававшуюся нере-
шенной. Метод эллипсоидов имеет совершенно другую, некомби-
наторную природу, нежели симплекс-метод. Однако в вычисли-
тельном плане этот метод оказался неперспективным. Тем не менее 
сам факт полиномиальной сложности задач привел к созданию це-
лого класса эффективных алгоритмов ЛП — методов внутренней 
точки, первым из которых был алгоритм Н. Кармаркара, предло-
женный в 1984 году. Алгоритмы этого типа используют непрерыв-
ную трактовку задачи ЛП, когда вместо перебора вершин много-
гранника решений задачи ЛП осуществляется поиск вдоль траекто-
рий в пространстве переменных задачи, не проходящих через вер-
шины многогранника. Метод внутренних точек, который в отличие 
от симплекс-метода обходит точки из внутренней части области 
допустимых значений, использует методы логарифмических барь-
ерных функций нелинейного программирования, разработанные
в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).