Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Симплекс-метод: есть ли на форуме


Автор: Гость_Lios 11.5.2005, 01:41
С алгоритмом и я знакома, даже уже запрограммировала его, НО!.. к сожалению, он работает неверно.
Программирую в Дельфи.

Если есть (люди : ), то есть смысл задать более конкретные вопросы...

Заранее благодарю!

Автор: Lios 11.5.2005, 01:50
Это был вовсе не гость, а вполне зарегистрированный юзер (т.е. ламер) -- я : )

Да, ошибку искала, но не нашла. Есть вероятность, что в том варианте алгоритма, который программировала, есть злобная опечатка, а я не настолько глубоко понимаю этот алгоритм, чтобы её заметить.

Автор: poor_yorik 11.5.2005, 09:06
Тогда лучше размести код алгоритма здесь, а мы попробуем найти все фичи, баги и глюки smile
smile Да кстати симплекс-метод для чего. Я знаю несколько его приминений smile

Автор: Mal Hack 11.5.2005, 09:09
http://forum.vingrad.ru/index.php?act=Search&CODE=show&searchid=379bace6e770accedc594b2952c0ecf0&search_in=posts&result_type=topics&highlite=%F1%E8%EC%EF%EB%E5%EA%F1

Автор: podval 11.5.2005, 11:23
Цитата(Lios @ 11.5.2005, 02:50)
Есть вероятность, что в том варианте алгоритма, который программировала, есть злобная опечатка

Ну и где этот вариант?

И, как верно замечено, пользуйся поиском по форуму.

Автор: Lios 28.5.2005, 01:33
Люди!!! Простите за "невнимание"! Почему-то не получала уведомлений, что есть ответы! Спасибо за готовность помочь.
Сегодня ещё раз попробую сама, а в случае неудачи -- размещу код здесь.
Кстати, насчёт разных модификаций, я уже пробовала и прямой, и двойственный, и табличный и т.д.

Но у меня сейчас голова идёт крУгом, до защиты осталось всего ничего, а прога не доделана!.. И мне до боли надоела моя программа : ), поэтому было не сосредоточиться...

Если сегодня не разберусь (очень постараюсь разобраться), то завтра код выложу!

Автор: Golden Hands 28.5.2005, 01:40
Выложи код пожалста, хочу его. smile

Автор: Lios 29.5.2005, 03:42
Вот, выкладываю... пока не то, чего я хочу : (

Краткое описание задачи.
Матрица А линейных ограничений -- постоянна. Размер 110х10 (110 неравенств, 10 переменных). Мн-во целевых ф-ий -- строки массива VectsC; для каждой из ц.ф. надо найти максимум и минимум на мн-ве ограничений. Правые части -- VectB. Не постоянный. Есть значения пр.ч. "по умолчанию" -- это если пользователь проги не ввёл никаких данных. Если ввёл, то "умалчиваемые" значения меняются на пользовательские и получившееся мн-во неравенств проверяется на непротиворечивость (т.е. мн-во ограничений на непустоту) -- здесь этого нет. Знаки неравенств: первые 55 <=, остальные -- >=. Поэтому матрица ограничений для 110 дополн. переменных -- имеет вид diag(1,...,1,-1,...,-1), остальные компоненты -- нули.
Поскольку я ещё работаю над этой пр-рой, то она довольно-таки "лохматая", причёсывать буду, когда заработает... В ней много лишнего, заранее прошу простить за неудобочитаемость! Но, надеюсь, мои комменты помогут быстро разобраться, что к чему и почему.

Да, ещё! В симплекс-методе опущена проверка ц.ф. на неограниченность, т.к. мн-во заведомо ограничено и никакие действия пользователя не могут сделать его неограниченным.

Код

procedure TFormHox.BtnCalcClick(Sender: TObject);  
var
  MatrA:    array [0..110, 1..120] of integer;        {матрица А ограничений(расширенная)}
  VectsC:   array [1..55, 1..10] of Byte;             {векторы С:кажд.стр - 1ые 10 коэф-тов ц.ф.}
  VectC:    array [1..120] of integer;                {вектор С коэфф-тов ц.ф.}
  VectN:    array [1..110] of integer;                {вектор N номеров баз.переменных}
  VectFopt: array [1..110] of real;                   {вектор максимумов (55) и минимумов(55)}
  ST: array [0..110, -1..120] of real;                                            {симплекс-таблица}
                        //нулевая строка СТ: номер итерации, значение ц.ф., коэфф-ты ц.ф.
                        //-1-ый столбец -- номера базисных компонент
                        //0ой стлб -- пр.части ограничений
                        //остальное -- коэф-ты ограничений

  El, lambda: real;       {макс (или мин) эл-т нулевой стр., мин отн-ия}
  divST, multST: real;       {вед. эл-т, мн-ль при пересчёте}
  p, r: integer;             {номер,вв. в базис, и номер, выв. из базиса}

  i, {j,} k,   {переменные для некоторых циклов}
  iC, jC,      {номер строки и номер столбца массива VectsC или номерa компонент вектора VectC}
  iA, jA,      {номер строки и номер столбца матрицы А}
  i_N, iB, jB, {номер эл-та массива N базисных номеров, вектора b пр.частей, матрицы В}
  iST, jST     {номер эл-та симплекс-таблицы}
  : integer;

const
  eps: real = 1e-10;
  VectBlock: array [1..10] of integer = (55, 65, 74, 82, 89, 95, 100, 104, 107, 109);
  DefaultB: array [1..110] of integer =
   (990,991,992,993,994,995,996,997,998,999,990,991,992,993,994,995,996,997,998,990,
    991,992,993,994,995,996,997,990,991,992,993,994,995,996,990,991,992,993,994,995,
    990,991,992,993,994,990,991,992,993,990,991,992,990,991,990,  1,  2,  3,  4,  5,
      6,  7,  8,  9, 10,  1,  2,  3,  4,  5,  6,  7,  8,  9,  1,  2,  3,  4,  5,  6,
      7,  8,  1,  2,  3,  4,  5,  6,  7,  1,  2,  3,  4,  5,  6,  1,  2,  3,  4,  5,
      1,  2,  3,  4,  1,  2,  3,  1,  2,  1);
          {значение вектора b "по умолчанию", если не введено ни одного инт-ла}
  CountIter: real = 116068178638777;  //це из н по м = це из 120 по 110 (макс число вершин (+1))
//пожалуй, нужна другая проверка на зацикливаемость. М.б. запоминать предыдущее значение ф-ии
//и вычислять разность предыдущего и последующего значений. Если она = 0 (меньше епсилон)
//в течение некоторого количества итераций (подумать, какого), то возможна зацикленность.
begin
  if Language = 'En' then
    StBar.SimpleText := 'Main data processing. This operation may take a while to complete.'
  else StBar.SimpleText := 'Основная обработка данных. Может потребовать длительного времени.';

  for iC := 1 to 110 do for jC := 1 to 10 do VectsC[iC, jC] := 0;
  for jC := 1 to 10 do begin
    k := 0;
    for iC := VectBlock[jC] - 54 to VectBlock[jC] - 54 + (10 - jC) do begin
      for i := jC to jC + k do VectsC[iC, i] := 1;
      k := k + 1
    end {for iB}
  end; {for jA}          //Заполнили VectsC
                                      //A
  for iA := 0 to 110 do for jA := 1 to 120 do MatrA[iA, jA] := 0;
  for iC := 1 to 55 do for jC := 1 to 10 do begin  //заполняем первые 10 столбцов матрицы А
    MatrA[iC, jC] := VectsC[iC, jC];
    MatrA[iC + 55, jC] := VectsC[iC, jC]
  end;
  for iA := 1 to 55 do begin
    MatrA[iA, iA + 10] := 1;
    MatrA[iA + 55, iA + 65] := -1 //заполняем последние 110 столбцов матрицы А
  end;
                                    //N: начальный базис -- мн-во баз.номеров
  for i_N := 1 to 110 do VectN[i_N] := i_N + 10;
                           //b: Заполняем и проверяем на непротиворечивость.
  VectB[0] := 0;
  for iB := 1 to 110 do VectB[iB] := DefaultB[iB];
  ChangeComponents;    //Изменили компоненты "по умолчанию" на введённые пользователем
  bContr := false;
  for iB := 1 to 55 do if VectB[iB] < VectB[iB + 55] then begin bContr := true; break end;
  if not bContr then ContradictionSearch;   //Проверили  b на непротиворечивость.
                                            //СМ
  for iC := 1 to 110 do VectFopt[iC] := VectB[iC];
  if not bContr then begin                         //Если схемы непротиворечивы
  
////////////////////////////////////////begSM
    for iC := 1 to 55 do begin                 //повт.55 раз для всех строк-ц.ф. с +ом

      for jC := 1 to 10 do VectC[jC] := VectsC[iC, jC]; //опр. ц.ф.

      ST[0, -1] := 0;  //№ итерации
      for jST := 1 to 120 do ST[0, jST] := -VectC[jST];   //ц.ф. 

      for iST := 1 to 110 do begin
        ST[iST, -1] := iST + 10;   //базис
        ST[iST, 0] := VectB[iST];  //пр.часть
        for jST := 1 to 120 do ST[iST, jST] := MatrA[iST, jST];
      end; //for iST
      for jST := 11 to 120 do ST[0, jST] := 0; 
      ST[0, 0] := 0;  //значение ц.ф.
                                              // Заполнили СТ
      p := 0;
      while p = 0 do begin
        El := -eps;
        for jST := 1 to 120 do
          if (ST[0, jST] < -eps)and(ST[0, jST] < El) then begin
              El := ST[0, jST];
              p := jST                             //№, вв в базис
            end;  
        if p > 0 then begin    //если зн.ц.ф. не макс
          lambda := 2147483647;
          for iST := 1 to 110 do
            if ST[iST, p] > eps then
              if lambda > ST[iST, 0]/ST[iST, p] then begin
                lambda := ST[iST, 0]/ST[iST, p];
                r := Round(ST[iST, -1]);             //№, выв из базиса
                i := iST;                            //№ вед.стр.
              end; //if lambda
          divST := ST[i, p];                         //ведущий элемент
                                             //пересчёт СТ
          ST[0, -1] := ST[0, -1] + 1;
          ST[i, -1] := p;

          for jST := 0 to 120 do ST[i, jST] := ST[i, jST]/divST; //пересч.вед.стр

          for iST := 0 to 110 do
            if iST <> i then begin
              MultST := ST[iST, p];
              for jST := 1 to 120 do
                ST[iST, jST] := ST[iST, jST] - MultST*ST[i, jST];
            end;
          p := 0;

        end //if p
        else p := 121;
      end; //while p

      VectFopt[iC] := Round(ST[0, 0]);
    end;  //for iC с +ом
////////////////////////////////////////endSM

    for iC := 1 to 55 do begin    {повторяем 55 раз для всех строк-ц.ф. на мин}
      for jC := 1 to 10 do VectC[jC] := -VectsC[iC, jC];//определили ц.ф.
                   //Здесь ищем мин значение ц.ф.
    end;  {for iC на мин}
  end; {if bContr}

  if bContr then
    if Language = 'En' then ShowMessage('An interval contradiction is found in the schemes.')
    else ShowMessage('В схемах найдены противоречия.');
  StBar.SimpleText := '';
  BtnCalc.Enabled := false;
end;


P.S. А как это вам код удаётся выложить красиво?? НаучИте, а?.. : )
P.P.S. О! Каэтся, я знаю, как вы это делаете! Не кнопочка ли "код"?
P.P.P.S. Получилось.... : )

Утро вечера мудренее! Нашла ошибку -- исправляю, пока никто не видит : )) Но всё равно что-то не то, похоже... на х1 > 100 и х1 + х2 < 600, например, выдаёт х1 < 600 и х2 < 600... а должна показывать х2 < 500...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)