N. Eriashvili Second Edition t e X tb o o k юн ити u n I t y moscow • 2000

xi, Х
2
,
*з, 
Х
4
, xs, Хб, х
7
— количества прутков, раскраи­
ваемых по каждому варианту. Тоща целевая функция имеет вид:
f { x )
—
6 0 * 2
+ 
50*3 
+ 
ЗОХ
4
+
20
x
5
+ 
lOxg 
-* 
m in .
Такое уравнение действительно при следующих условиях:
2х\ + Х
2
+ 
хз
= 150 тыс.;
Х
2
 + 
3
x
4
 + 
2
x
5
 + хб = 140 тыс.;
xi + х
2
 + х
3
 + 
2
х
5
 + 4хб + 
6
x
7
 = 48 тыс.;
xj
г 0; 
Xj
= 0; 
j
= 1,7.
Задача о коммивояжере. Здесь требуется отыскать наилуч­
ший маршрут, с тем чтобы объехать все порученные комми­
вояжеру пункты и вернуться назад либо в кратчайший срок, 
либо с наименьшими затратами на проезд. В общем виде эту 
задачу можно сформулировать следующим образом.
Имеется я городов, занумерованных числами от 1 до я. 
Коммивояжер, выезжая из города 1, должен побывать в каждом 
городе ровно один раз и вернуться в исходный пункт. Извест­
ны расстояния между городами: 
Су
(/, 
j
= 
1
,л;/ 
* j )
. Требуется 
найти самый короткий маршрут.
Введем переменные:
1
, если в маршрут входит переезд из города / в городу;
Ху
= 
,
— ,
0
, в противном случае 
\i *■ j; i , j
= 
1
,n)J.
Требования однократного въезда и выезда из каждого горо­
да запишутся в виде:
2 * 0 - 1 ; У - Г я ;
(25.47)
/-1
Я 
____
2