Оптимальная загрузка танкера))

[de-sed]

Бразеры, помогите разобраться!

Работаю на танкерах. Постоянно возникает задача оптимальной загрузки, которую пытался решить с помощью экселя, но не хватает знаний) Суть задачи: требуется загрузить танкер, например, тремя сортами разного груза (бензин, соляра, керосин). Известны массы (объемы) грузов (они, как правило, разные), количество и объем грузовых танков. Единственное ограничение - танки нельзя грузить больше 98% от их максимального объема. Требуется так оптимально разместить эти грузы, чтобы танки были загружены по максимуму (т.е. чтобы максимально использовать полезный грузовой объем с учетом вышеназванного 98%-го ограничения). Прикидка вручную подчас занимает много времени, поэтому хотелось бы немного облегчить себе жизнь и как-нибудь автоматизировать этот процесс) Знаю, что все это можно реализовать с помощью Solvera, встроенного в Excel, но, повторюсь, не хватает знаний на запрограммирование алгоритма. Спасибо заранее за любые возможные советы.

[meteese]

Задача подобна задаче логистики (в городе есть несколько складов с убывающими товарами; нужно снабжать склады грузовиком с наименьшей суетой) или задача о рюкзаке (тяжелое вниз, легкое наверх, дешевое вниз, дорогое наверх, мягкое к спине, нужное первым на выход). Сейчас такого рода задачи решаются только перебором, на компьютере. Есть специальная программа
http://www.packer3d.ru/node/170
Больше сказать ничего не могу и этой темой не интересуюсь.

[Sender]

То есть у вас на каждом танкере имеются танки разного объёма, и вам надо разместить по ним заданные объёмы наливных грузов, максимизировав при этом суммарный объём танков, оставшихся пустыми?

[vvvv]

de-sed в сообщении #529109 писал(а):

Бразеры, помогите разобраться!

Работаю на танкерах. Постоянно возникает задача оптимальной загрузки, которую пытался решить с помощью экселя, но не хватает знаний) Суть задачи: требуется загрузить танкер, например, тремя сортами разного груза (бензин, соляра, керосин). Известны массы (объемы) грузов (они, как правило, разные), количество и объем грузовых танков. Единственное ограничение - танки нельзя грузить больше 98% от их максимального объема. Требуется так оптимально разместить эти грузы, чтобы танки были загружены по максимуму (т.е. чтобы максимально использовать полезный грузовой объем с учетом вышеназванного 98%-го ограничения). Прикидка вручную подчас занимает много времени, поэтому хотелось бы немного облегчить себе жизнь и как-нибудь автоматизировать этот процесс) Знаю, что все это можно реализовать с помощью Solvera, встроенного в Excel, но, повторюсь, не хватает знаний на запрограммирование алгоритма. Спасибо заранее за любые возможные советы.

По вашему описанию, вообще, никакой задачи не видно.Что вы понимаете под словом "оптимально"? В чем заключаются ваши трудности? Изложите по-подробней.

[Praded]

vvvv в сообщении #529213 писал(а):

Изложите по-подробней.

Больше всего непонятно, можно ли в танк, где ранее перевозили соляру, наливать бензин?

[ИСН]

Можно, но эта операция имеет свою цену (т.е. входит в функционал, который мы минимизируем - если по-хорошему).

[Maslov]

Sender в сообщении #529198 писал(а):

То есть у вас на каждом танкере имеются танки разного объёма, и вам надо разместить по ним заданные объёмы наливных грузов, максимизировав при этом суммарный объём танков, оставшихся пустыми?

Это, на мой взгляд, не совсем полная постановка. Например, рассмотрим случай, когда необходимо перевезти 3 кубометра бензина, и есть танки с полезной емкостью 1 кубометр, 2 кубометра и 3 кубометра. Можно залить первый и второй, можно - только третий. Суммарный объем пустых танков в обоих случаях будет одинаковым, но с содержательной точки зрения какой-то вариант является предпочтительным.

(Под полезным объемом понимается 98% номинального)

-- Пт янв 20, 2012 15:15:53 --

de-sed в сообщении #529109 писал(а):

Единственное ограничение - танки нельзя грузить больше 98% от их максимального объема.

de-sed, а что, никаких ограничений по неравномерности загрузки танков нет?

[de-sed]

Спасибо всем откликнувшимся!
Немного уточнений: да, танки имеют разный объём (от 1200 до 2000 куб. метров). Грузы имеют определенные заданные объемы. Например требуется загрузить 10000 куб. метров бензина, 8000 куб. метров керосина и 6000 куб. метров солярки. В сумме - это чуть меньше полной грузовместимости судна. Смысл задачи в том, чтобы максимально полезно задействовать полезный грузовой объем танкера. Например, может получиться, что бензин будет загружен в 1, 3, 6 танки, занимая 96% от их суммарного объема - это хороший показатель. Если грузить в 2, 4, 5 - то будет перелив, так объемы этих танков меньше, чем в первом варианте. Если же, например, грузить в 3, 5, 6, то общее заполнение танков будет лишь на 80%, т.е почти 20% полезного грузового объема не будет использовано, а другой груз одновременно с бензином в один танк грузить нельзя. Порой такая прикидка по оптимальному размещению нескольких грузов занимает достаточно много времени и хотелось бы как-нибудь все это дело автоматизировать. Надеюсь, что расписал все понятно))

[Praded]

ИСН в сообщении #529224 писал(а):

Можно, но эта операция имеет свою цену (т.е. входит в функционал, который мы минимизируем - если по-хорошему).

Теперь я понимаю смысл объявления: "Продаётся цементовоз-молоковоз".

-- Сб янв 21, 2012 17:14:11 --

de-sed в сообщении #529479 писал(а):

Надеюсь, что расписал все понятно

А нельзя привести конкретный живой пример, если это не является закрытой информацией?

[Yu_K]

2 Praded

http://korabley.net/news/samii_bolshoi_tanker_v_mire_batillus/2009-06-03-257
Самый большой танкер в мире «Batillus»

http://www.svarchik.ru/vodny.htm
Основные данные морских танкеров
Основные данные несамоходных речных барж
Основные данные речных танкеров

http://www.odin.tc/disaster/big.asp
Самый большой танкер LNG в мире
Гигант Mozah, проекта Q-Max, берет 266000 кубометров – достаточно, чтобы обеспечит теплом и электричеством всю Англию в течении 24 часов. Дедвейт Mozah 125600 тонн, длина 345 метров, ширина 50 метров, осадка 12 метров. От киля до клотика высота судна равна высоте 20-этажного небоскреба. Сжиженный газ перевозится в пяти гигантских танках мембранного типа, но только размерами новинки лидера газовозов не ограничиваются.

[Praded]

Yu_K
Но ведь ТС ходит на конкретном судне, а не на всём разнообразии.

[Sender]

В общем, вырисовывается задача целочисленного линейного программирования. Пусть у нас есть $n$ грузов и $m$ танков, объёмы грузов $\{V_1,...,V_n\}$, полезные объёмы танков (исходные, умноженные на 0,98) $\{c_1,...,c_m\}$. Введём переменные $x_{ij},x_{ij}\in \{0,1\}, i\in\overline{1,n}, j\in\overline{1,m}$, где $x_{ij}=1$ в том и только в том случае, если в j-м танке содержится i-й груз. Тогда условия задачи записываются так:
1. $0\leqslant x_{ij}\leqslant 1, i\in\overline{1,n}, j\in\overline{1,m}.$

2. $\sum_{i=1}^{n}x_{ij}\leqslant 1, j\in\overline{1,m}$ (каждый танк загружается не более, чем одним видом груза).

3. $\sum_{j=1}^{m}c_{ij}x_{ij}\geqslant V_i, i\in\overline{1,n}$ (каждый груз полностью распределён по танкам).

4. $\sum_{i=1}^{n}\sum_{j=1}^{m}c_{ij}x_{ij}\rightarrow \min$ (условие максимизации загруженности танков).

Эксель ведь позволяет решать целочисленные задачи подобного типа?

[vvvv]

de-sed в сообщении #529479 писал(а):

Спасибо всем откликнувшимся!
Немного уточнений: да, танки имеют разный объём (от 1200 до 2000 куб. метров). Грузы имеют определенные заданные объемы. Например требуется загрузить 10000 куб. метров бензина, 8000 куб. метров керосина и 6000 куб. метров солярки. В сумме - это чуть меньше полной грузовместимости судна. Смысл задачи в том, чтобы максимально полезно задействовать полезный грузовой объем танкера. Например, может получиться, что бензин будет загружен в 1, 3, 6 танки, занимая 96% от их суммарного объема - это хороший показатель. Если грузить в 2, 4, 5 - то будет перелив, так объемы этих танков меньше, чем в первом варианте. Если же, например, грузить в 3, 5, 6, то общее заполнение танков будет лишь на 80%, т.е почти 20% полезного грузового объема не будет использовано, а другой груз одновременно с бензином в один танк грузить нельзя. Порой такая прикидка по оптимальному размещению нескольких грузов занимает достаточно много времени и хотелось бы как-нибудь все это дело автоматизировать. Надеюсь, что расписал все понятно))

Вот сейчас смысл задачи ясен.

Не могли бы указать количество танков и их емкость, а также максимальное число различных перевозимых грузов одновременно.

Под целочисленное линейное программирование эта задача не подходит.
Можно попытаться написать для этой задачи отдельную программу.

[Sender]

vvvv в сообщении #530336 писал(а):

Под целочисленное линейное программирование эта задача не подходит.

Если не трудно, не могли бы вы указать на ошибку в моих построениях?

[Praded]

Sender в сообщении #530358 писал(а):

Если не трудно, не могли бы вы указать на ошибку в моих построениях?

Ведь одного груза может быть на 1,5 танка...