Несбалансированная транспортная задача с дефицитом

В районе имеется 4 песчаных карьера, с которых песок вывозится на 5-тонных грузовиках. Предприятия-поставщики S1 - S4 разрабатывающие карьеры, могут поставлять определенное количество грузовиков с песком в день.

В этом районе имеется 5 заводов железобетонных конструкций - потребителей песка D1-D5, которым требуется определенное количество грузовиков с песком в день. Стоимости перевозки песка одним грузовиком от карьера-поставщика Si к заводу-потребителю Di(в условных единицах) приведены в таблице параметров.

Требуется:

1. Составить план перевозок, минимизирующий затраты.

2. Составить план перевозок, максимизирующий затраты. Найти разность между наибольшими и наименьшими из возможных затратами.

3. Указать на каком из трех заводов не получит песок в нужном объеме.

4. Как изменится оптимальный план, если маршрут от S2 к D4 запрещен.

Задача о минимизации пробега автомобилей.

Фирма, занимающаяся перевозкой грузов собственных автомобилях КамАЗ, обслуживает своих клиентов в центральных городах России. Клиенты могут заказать фирме доставку груза из любого населенного пункта в любой город. После доставки КамАЗы ждут распоряжений диспетчера о выполнении следующей заявки в том городе, куда был доставлен груз.

В настоящий момент 4 порожних автомобиля ждут распоряжений в Иваново, 3 автомобиля - в Костроме, 6 машин - в Орле и одна - в Калуге. Одновременно диспетчеру поступили заявки на 5 автомобилей во Владимире, на 3 автомобиля в Санкт-Петербурге и на 6 автомобилей в Москве. Расстояния между городами известны и приведены в таблице.

Требуется:

1). Составить такой план перегона порожних автомобилей из мест их расположения к клиентам, чтобы суммарный пробег всех автомобилей, а следовательно, и издержки фирмы были минимальными.

2). Выяснить, как изменится оптимальный план, если стало известно, что в Калуге освободилась еще одна машина, а в Москве появился дополнительный заказчик.