Варианты 7–12. Условие

С трёх складов, расположенных в Химках, на Сходне и в Ховрино, необходимо доставить в пять магазинов сахарный песок в соответствии с заявкой каждого магазина. Объёмы запасов песка, имеющегося на складах, объёмы заявок магазинов и тарифы на поставку одной тонны груза со складов в магазины даны в таблице.

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Три склада (A1:A3) поставляют в три магазина (B1:B3) розничной сети некоторый товар. Запасы данного товара на складах (шт.), потребности в нем магазинов (шт.)и тарифы на перевозку (в расчете на 1 шт.) показаны в транспортной таблице ниже. Найдите оптимальный план грузоперевозок, обеспечивающий удовлетворение потребностей магазинов в товаре с минимальными издержками на его транспортировку.

Вариант 14

Два поставщика (A1:A2) обеспечивают четыре завода (B1:B4) необходимым для производства продукции сырьем. Запасы сырья на складах поставщиков (т.), потребности в нем заводов (т.) и тарифы на перевозку (в расчете на 1 т.) приведены в транспортной таблице ниже. Найдите оптимальный план грузоперевозок, обеспечивающий удовлетворение потребностей заводов в сырье с минимальными издержками на его транспортировку.

Вариант 15

Груз, хранящийся на четырех складах С1 (С1 — склад 1), С2, С3, С4, необходимо развести по 6-ти магазинам М1 (М1 — магазин 1), М2, М3, М4, М5, М6. Для перевозки грузов требуется 45,40,45,50 автомашин соответственно. Первому магазину требуется 24 машин груза, второму — 32, третьему — 18, четвертому — 17, пятому — 22 и шестому — 27 машин. Стоимость пробега одной автомашины за 1 км составляет 7 ден. ед. Составьте оптимальный по стоимости план перевозки грузов со складов до магазинов. Расстояния от складов до магазинов указаны в следующей таблице.

	М1	М2	М3	М4	М5	М6
С1	3	4	5	4	11	5
С2	2	7	3	7	3	2
С3	1	3	3	2	8	8
С4	3	2	7	4	5	11

Вариант 16

С трёх складов, расположенных в Химках, на Сходне и в Ховрино, необходимо доставить в пять магазинов сахарный песок в соответствии с заявкой каждого магазина. Объёмы запасов песка, имеющегося на складах, объёмы заявок магазинов и тарифы на поставку одной тонны груза со складов в магазины даны в таблице.

6 Задача коммивояжера

Имеется nгородов. Выезжая из исходного городаА₁, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в городА₁. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности — стоимость проезда, время в пути, суммарное расстояние и т.д.

6.1 Математическая модель

Пусть задана матрица T=||t_ij||, в которой задано время, затрачиваемое на переезд между городами, и требуется минимизировать время в пути.

Введем булевы переменные:

, если коммивояжер переезжает из городаА_iв городА_j,i ≠ j;

, в противном случае,.

Целевая функция имеет вид: .

ЦФ представляет собой суммарное время в пути.

Ограничения имеют вид:

, (1)

_{, (2)}

Так как нельзя непосредственно возвращаться из города i в городi, то.

Исключение подциклов длины меньшей n задается условием

_{, (3)}

где — неограниченные действительные переменные.

Условия (1) означают, что коммивояжер выезжает из каждого города один раз, а условия (2) — что он въезжает один раз в каждый город. Условия (3) предназначены обеспечить связность маршрута коммивояжера. Более точно, эти условия запрещают любой цикл, не проходящий через город 1, и тем самым исключают ситуации, подобные приведенной на рисунке.