АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
Регистрация  ||  Вход/выход
Забыли пароль?
Рейтинг авторов
 
О системе
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

2013. Транспортная задача

Ограничение времени: 2 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Имеется три склада с запасами продукции на них S1, S2 и S3 тонн. Эту продукцию нужно доставить 3 потребителям, потребности которых составляют D1, D2 и D3 тонн.

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

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

Первая строка входных данных содержит три вещественных числа S1, S2, S3 – количества продукции на складах.

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

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

Все входные числа лежат в диапазоне от 0 до 1000. Гарантируется, что S1 + S2 + S3 ≥ D1 + D2 + D3.

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

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

Пример

Входные данные
35.5 70 55
40.5 60 60
8 6 5
1 4 3
2 7 6
Выходные данные
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

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Учебные курсы / Исследование операций / Линейное программирование /
2012. 03 - Выплавка стали 2013. 1809. 05 - Продажа огурцов
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.