AVT VSU - Problem 2013. Transport Problem

2013. Transport Problem

Time Limit:	2 seconds
Memory Limit:	262144KB
Points:	100

Имеется три склада с запасами продукции на них S₁, S₂ и S₃ тонн. Эту продукцию нужно доставить 3 потребителям, потребности которых составляют D₁, D₂ и D₃ тонн.

Составить план перевозок, при котором затраты на перевозку минимальны, все потребности удовлетворены. Тарифы перевозок заданы матрицей C, где C_ij – стоимость доставки одной тонны груза со склада i потребителю j.

Входные данные

Первая строка входных данных содержит три вещественных числа S₁, S₂, S₃ – количества продукции на складах.

Вторая строка входных данных содержит три вещественных числа D₁, D₂, D₃ – потребности каждого из потребителей (где 1 ≤ D₁, D₂, D₃ ≤ 1000).

Следующие три строки содержат по три вещественных числа – элементы матрицы C.

Все входные числа лежат в диапазоне от 0 до 1000. Гарантируется, что S₁ + S₂ + S₃ ≥ D₁ + D₂ + D₃.

Выходные данные

Выведите одно вещественное число – наименьшую суммарную стоимость перевозок. Абсолютная или относительная погрешность ответа не должна превышать 10^- 4

Пример

Входные данные

Выходные данные

615.500000

Примечание

В примере возможен следующий оптимальный план перевозок:

0 17.75 17.75
0 35 35
40.5 7.25 7.25

При решении задач методом линейного программирования вы можете воспользоваться библиотеками scipy, cvxopt и linprog для Python, а также языком GNU Octave. Пример решения задачи с использованием linprog можно посмотреть здесь: pastebin.com/qgFix2Qi. Примеры использования SciPy, cvxopt и Octave приведены в методических указаниях.

Для написания и отладки кода можно использовать следующие web-ресурсы:
для Octave/Matlab: www.tutorialspoint.com/execute_matlab_online.php
для Python: http://primat.org/index/0-144

Remote Training on Programming

2013. Transport Problem