На сборе в пятом-б

гам сети, при которых из входа сети в ее выход будет перевезена 1 единица груза, а суммарная стоимость перевозок будет минимальна.

Перевозка $x_{ij}$ единиц груза по дуге $i-j$ стоит $c_{ij}x_{ij}$.

Поэтому общие затраты на перевозку равны

$$S = \sum_{i,j} c_{ij} x_{ij}. \tag{17}$$

Нужно найти такие значения величин $x_{ij}$, при которых $S$ принимает наименьшее из возможных значений и которые удовлетворяют условиям:

а) непрерывности потока в промежуточных узлах (см. (3));

б) неотрицательности объемов перевозок: $x_{ij} \geqslant 0$;

в) равенства единице суммарного потока по сети:

$$X = x_{12} + x_{13} + x_{35} + x_{45} = 1. \tag{18}$$

Для построения электрической модели транспортной сети этой задачи нужно заменить каждую дугу $i-j$ ветвью с последовательно включенными диодом и источником напряжения, величина которого численно равна $c_{ij}$, а в дополнительную ветвь из выхода на вход сети включить единичный источник тока. Соответствующая схема представлена на рисунке 6.

Можно доказать…

Но нам уже пора поставить точку. Читатели, заинтересовавшиеся этими вопросами, могут попробовать свои силы, решая следующие

Упражнения

1. Докажите, что токи $x_{ij}$, которые устанавливаются в ветвях электрической цепи, изображенной на рисунке 6, дают решение задачи минимизации транспортных затрат.

2. Докажите, что каждый ненулевой ток по ветви этой цепи обязательно равен 1, т. е. что в действительности ток не разветвляется в узлах, а идет от входа к выходу по определенному пути («путь минимальных затрат»).

3. Используя задачу о минимизации транспортных затрат, покажите, как с помощью той же модели (рис. 6) можно определить кратчайший путь по дугам транспортной сети, ведущий от входа к выходу.

2 Квант № 2

На сборе в пятом-б

— Сегодня я покажу вам фокус, — объявила пионервожатая Лена. — Согласны?

— Согласны! — послышались голоса пятиклассников.

— А какой фокус? — спросил Сережа. — Я тоже знаю фокус с иголкой…

— Я покажу арифметический фокус, — сказала Лена — Пусть каждый из вас задумает какую-нибудь цифру. Только мне не говорите, — объявила Лена. Теперь умножьте это число на 5. К произведению прибавьте 4 и удвойте полученную сумму. Готово?

— Теперь прибавьте еще 99, — сказала Лена, — и у каждого из вас получится трехзначное число. Оставьте в этом числе только последнюю цифру, а первые две зачеркните.

— Как это: зачеркнуть? — спросил Юра.

— Например, у тебя получилось число 364, — сказала Лена. — Если зачеркнуть первые две цифры, то останется только 4.

— К тому, что осталось, продолжала Лена, — прибавьте 28, а потом разделите на 5.

Соня, сидевшая на последней парте, быстро сосчитала и рассмеялась.

— Почему ты смеешься? — спросила Лена. — Иди сюда. — И она тихонько сказала Соне на ухо:

— У тебя получилось 7.

— Верно, — обрадовалась Соня. — А как ты узнала?

— А у меня сколько получилось? — нетерпеливо спросил Сережа.

Лена подошла к нему и тихонько сказала:

— У тебя получилось 7.

Потом Лена подошла ко всем по очереди и каждому сказала:

— У тебя получилось 7.

---

Как Лена могла узнать, что у каждого получилось семь?

17