VPF::[Все языки] Минимальная стоимость перевозок

duk

Дата 20.9.2007, 16:54 (ссылка)

(нет голосов)

Загрузка ...

Some Object

Профиль
Группа: Участник
Сообщений: 179
Регистрация: 19.7.2007

Репутация: нет
Всего: 4

Ни у кого нету исходника нахождения минимальной стоимости перевозок (закрытая транспортная задача)? Если есть поделитесь.

Akina

Дата 20.9.2007, 17:03 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454

разрисовываешь матрицу доставок в Экселе, напускаешь на нее решатель, задав граничные условия (скажем, неотрицательность перемещений) - и получаешь решение.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

duk

Дата 20.9.2007, 17:19 (ссылка)

(нет голосов)

Загрузка ...

Some Object

Профиль
Группа: Участник
Сообщений: 179
Регистрация: 19.7.2007

Репутация: нет
Всего: 4

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

comtat

Дата 20.9.2007, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1310
Регистрация: 2.5.2006
Где: Россия, Казань

Репутация: 8
Всего: 71

Поиск рулит

--------------------

Рожденный в СССР !!!
ExtJS - мой фреймворк

ne0n

Дата 20.9.2007, 17:36 (ссылка)

(нет голосов)

Загрузка ...

PlayBoy

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 5.8.2005
Где: Н.Новгород

Репутация: нет
Всего: 11

Цитата(duk @ 20.9.2007, 17:19

)

мне исходник нужен.

на каком языке?!

Это сообщение отредактировал(а) ne0n - 20.9.2007, 17:37

--------------------

http://sa-sec.org
как я вам? smile

duk

Дата 20.9.2007, 17:43 (ссылка)

(нет голосов)

Загрузка ...

Some Object

Профиль
Группа: Участник
Сообщений: 179
Регистрация: 19.7.2007

Репутация: нет
Всего: 4

comtat, то что в поиске это не полное решение, опорный план обычно делается более оптимальным путем использования циклов. вот именно это мне нужно

Добавлено через 13 минут и 18 секунд
ne0n, c/c++, c#, pascal/delphi без разницы

Guedda

Дата 20.9.2007, 20:08 (ссылка)

(нет голосов)

Загрузка ...

Подрывник

Профиль
Группа: Завсегдатай
Сообщений: 3137
Регистрация: 27.12.2005
Где: Ростов-на-Дону

Репутация: 6
Всего: 78

M
Guedda

Модератор: Название темы должно отражать ее суть!

--------------------

Ll 2

comtat

Дата 20.9.2007, 20:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1310
Регистрация: 2.5.2006
Где: Россия, Казань

Репутация: 8
Всего: 71

Цитата(duk @ 20.9.2007, 17:43

)

опорный план обычно делается более оптимальным путем использования циклов.

Опорный план считается методом северо-западного угла или метод потенциалов
Какой нужен ?

--------------------

Рожденный в СССР !!!
ExtJS - мой фреймворк

duk

Дата 20.9.2007, 23:02 (ссылка)

(нет голосов)

Загрузка ...

Some Object

Профиль
Группа: Участник
Сообщений: 179
Регистрация: 19.7.2007

Репутация: нет
Всего: 4

Guedda, это и есть суть задачи, если вы учили мат методы исследования операций, то вы наверняка должны знать что Т задача, носит еще и другое название, такое как "Задача про транспортировку грузов".

Добавлено через 5 минут и 41 секунду
comtat, получение опорного плана можно осуществить как минимум тремя способами (метод потенциалов - это метод улучшения готового опорного плана): северо-западного угла, минимального элемента, метод вычеркивания - расположены по мере возрастания результата. Получив опорный план, можно его усовершенствовать используя так называемы циклы. Вот как их организовать я вас и спрашиваю.

comtat

Дата 20.9.2007, 23:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1310
Регистрация: 2.5.2006
Где: Россия, Казань

Репутация: 8
Всего: 71

Цитата(duk @ 20.9.2007, 23:02

)

используя так называемы циклы.

Я 3 года изучал теории оптимизации, но что-то не помню ни каких циклов ...
Поясните, что это такое... хотя бы формальное определение

--------------------

Рожденный в СССР !!!
ExtJS - мой фреймворк

apook

Дата 21.9.2007, 00:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23

Алгоритм Дейкстры рулит

Код


// Алгоритм Дейкстры
// нахождение наименьшего расстояяния от заданной точки 
// до всех остальных
#include<iostream.h> 
#include<conio.h> 

#define M ( sizeof(cities)/sizeof(cities[ 0 ]) )
#define N ( sizeof(inf)/sizeof(inf[ 0 ]) )

//якобы бесконечность, данное число должно быть больше
//максимального расстояния (по правилам алгоритма)
#define INFINITY 10000
//от какой точки пляшем :)
#define dance 2

//пункты
char cities[ ][ 50 ]={ "A", "B", "C", "D", "E", "F" };

struct
{
     char points[ 2 ][ 50 ]; //от пункта к пункту
     int distance;           //расстояние км
     }inf[ ]={
     {{ "A", "B" }, 65 },
     {{ "B", "C" }, 40 },
     {{ "C", "D" }, 60 },
     {{ "D", "E" }, 68 },
     {{ "E", "A" }, 32 },

     {{ "A", "F" }, 45 },
     {{ "B", "F" }, 25 },
     {{ "C", "F" }, 40 },
     {{ "D", "F" }, 60 },
     {{ "E", "F" }, 50 }
     };

struct range
{
    char *point;    //пункт
    int distance;   //расстояние от начальной точки
};
 
int main() 
{
int i, j, c, current_distance, q, p, real_p;
char *current_city=NULL, line[ M ][ 50 ];


for( i=0; i<M; i++ )
    line[ i ][ 0 ]='\0';


range *xr=new range[ M ];
//расстояние от стартовой точки до остальных изначально
//равно бесконечности
for( i=0; i<M; i++ )
{
    xr[ i ].point=NULL;
    xr[ i ].distance=INFINITY;
    }
//а начальная имеет значение ноль
xr[ 0 ].distance=0;
xr[ 0 ].point=cities[ dance ];

for( i=0, c=0, p=1; i<M; i++ )
{
    current_city=xr[ i ].point;

    for( j=0, real_p=1; j<N; j++ )
    {
        current_distance=xr[ i ].distance;

        if( strcmp(inf[ j ].points[ 0 ], current_city)==0
        ||  strcmp(inf[ j ].points[ 1 ], current_city)==0 )
        {
            //проверка не проверяли ли эту точку ранее
            for( q=0; q<i; q++ )
                if( strcmp(inf[ j ].points[ 0 ], xr[ q ].point)==0
                ||  strcmp(inf[ j ].points[ 1 ], xr[ q ].point)==0 )
                    break;
            if( q<i )
                continue;

        //-----------------------------
        //находим какая точка сейчас явл соседом с той которую
        //проверяем т.е до какой точки смотрим расстояние
        for( q=0; q<2; q++ )
            if( strcmp(inf[ j ].points[ q ], current_city)!=0 )
                break;

        //i -- текущий пункт
        //p -- всего соседей(уже посещенных) 
        //real_p -- сосед текущего пункта который сейчас проверяется
        //j -- текущий отрезок
        //q -- олределяет каой из двух пунктов inf[ j ].points явл текущим
        //     и стал-быть какой есть сосед 
         for( c=0; c<p; c++ )
             if( strcmp(xr[ c ].point, inf[ j ].points[ q ])==0 )
                 break;
         if( c<p )
             real_p=c; //пункт посещался сверяться будем с ним  
         else
         {   //пункт не посещался
             xr[ p ].point=inf[ j ].points[ q ]; //запоминаем пункт
             real_p=p; //вносим свежие данные по нему
             ++p;
             }

        current_distance+=inf[ j ].distance;
        if( current_distance<xr[ real_p ].distance )
        { 
            //запоминаем расстояние
            xr[ real_p ].distance=current_distance;
            strcat( line[ real_p ], inf[ j ].points[ 0 ] );
            strcat( line[ real_p ], inf[ j ].points[ 1 ] );
            }

            }
        }
    }

cout << endl << "---------------------" << endl
     << "Beeline from " << xr[ 0 ].point << endl;
for( q=1; q<p; q++ )
   cout << "to: " << xr[ q ].point << " = " << xr[ q ].distance
        << " ( " << line[ q ] << " ) " << endl;


getch();
return 0; 
}

Здесь правда нахождение наименьшего расстояния но почти то, переделывать тоже некогда. Вместо расстояния взять стоимость и все!

Это сообщение отредактировал(а) apook - 21.9.2007, 00:53

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

duk

Дата 21.9.2007, 00:57 (ссылка)

(нет голосов)

Загрузка ...

Some Object

Профиль
Группа: Участник
Сообщений: 179
Регистрация: 19.7.2007

Репутация: нет
Всего: 4

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

comtat

Дата 21.9.2007, 11:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1310
Регистрация: 2.5.2006
Где: Россия, Казань

Репутация: 8
Всего: 71

Цитата(duk @ 21.9.2007, 00:57

)

циклом в данном случае будет замкнутая линия которая обьединяет несколько клеток в таблице

Это решение называется методом потенциалов

--------------------

Рожденный в СССР !!!
ExtJS - мой фреймворк

daemon003

Дата 27.12.2007, 02:12 (ссылка)

(голосов:1)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 27.12.2007

Репутация: нет
Всего: нет

авапвап

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »