Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members   Examples  

smplxtbl.h

Go to the documentation of this file.
00001 //N.Yu.Zolotykh 1999
00002 //University of Nizhni Novgorod, Russia
00003 //*******************************************************************
00004 // SmplxTbl.h
00005 //*******************************************************************
00006 
00007 #include<iostream.h>
00008 #include<conio.h>
00009 #include"matrices.h"
00010 #include"math.h"
00011 
00012 #if defined(__BORLANDC__) && !defined(__WIN32__)
00013 #include<values.h>
00014 #endif
00015 
00016 #ifndef SMPLXTBLS_H_
00017 #define SMPLXTBLS_H_
00018 
00024 
00027 
00030 
00033 
00036 
00041 
00042 template <class T> class simplex_table: public matrix<T>
00043 {
00044 public:
00045 
00047   simplex_table();
00048 
00050   index get_rows();
00052   index get_cols();
00054   index find_pivot_col();
00056   index find_pivot_row(index j);
00058   index find_pivot_row();
00060   index find_pivot_col(index i);
00062   index find_generating_row();
00064   index find_generating_row_mip();
00066   int is_primal_feasible();
00068   int is_dual_feasible();
00070   int primal_simplex_col();
00072   int dual_simplex_col();
00074   int gomory1();
00076   int gomory2();
00078   void pivoting_col(index pivot_row, index pivot_col);
00079 
00080 private:
00081 
00082   int old_cut_plane_deleting;
00083   int k;
00084   index is_non_bas_var(index j);
00085   index init_rows;
00086   vector<index> non_bas_var;
00087 
00088 };
00089 
00090 //*************************************************************************
00091 
00092 int is_integer(const double a)
00093 {
00094   const double delta = 0.00000005;
00095   if(fabs(floor(a + 0.5) - a) < delta) return 1;
00096   return 0;
00097 }
00098 
00099 //*************************************************************************
00100 
00101 template <class T> 
00102 simplex_table<T>::
  simplex_table():
00103     matrix<T>(),
00104     non_bas_var(),
00105     old_cut_plane_deleting(0)
00106 {
00107   cin >> k;
00108   cin >> *this;
00109   non_bas_var.resize(get_cols() + 1);
00110   init_rows = get_rows();
00111   for(index j = 1; j <= get_cols(); j++)
00112     non_bas_var[j] = j;
00113 }
00114 
00115 //*************************************************************************
00116 
00117 template <class T> inline index 
00118 simplex_table<T>::
  get_rows()
00119 {
00120   return get_m() - 1;
00121 }
00122 
00123 //*************************************************************************
00124 
00125 template <class T> inline index 
00126 simplex_table<T>::
  get_cols()
00127 {
00128   return get_n() - 1;
00129 };
00130 
00131 //*************************************************************************
00132 
00133 template <class T> index 
00134 simplex_table<T>::
  find_pivot_row()
00135 {
00136   for(index i = 1; i <= get_rows(); i++)
00137   {
00138     if(at(i, 0) < T(0)) return i;
00139   }
00140   return 0;
00141 }
00142 
00143 //*************************************************************************
00144 
00145 template <class T> index 
00146 simplex_table<T>::
  find_pivot_col(index pivot_row)
00147 {
00148   index j_max = 0;
00149   T max;
00150 
00151   index j;
00152 
00153   for(j = 1; j <= get_cols(); j++)
00154   {
00155     if(at(pivot_row, j) < T(0))
00156     {
00157       max = at(0, j) / at(pivot_row, j);
00158       j_max = j;
00159       break;
00160     }
00161   }
00162 
00163   if (!j_max)
00164     return 0;
00165 
00166   for(j = j_max + 1; j <= get_cols(); j++)
00167   {
00168     if((at(pivot_row, j) < T(0)) && (at(0, j) / at(pivot_row, j) > max) )
00169     {
00170       max = at(0, j) / at(pivot_row, j);
00171       j_max = j;
00172     }
00173   }
00174 
00175   return j_max;
00176 }
00177 
00178 //*************************************************************************
00179 
00180 template <class T> index 
00181 simplex_table<T>::
  find_pivot_col()
00182 {
00183   for(index j = 1; j <= get_cols(); j++)
00184   {
00185     if(at(0, j) < T(0)) return j;
00186   }
00187   return 0;
00188 }
00189 
00190 //*************************************************************************
00191 
00192 template <class T> index 
00193 simplex_table<T>::
  find_pivot_row(index pivot_col)
00194 {
00195   index i_min = 0;
00196   T min;
00197 
00198   index i;
00199   for(i = 1; i <= get_rows(); i++)
00200   {
00201     if(at(i, pivot_col) > T(0))
00202     {
00203       min = at(i, 0) / at(i, pivot_col);
00204       i_min = i;
00205       break;
00206     }
00207   }
00208 
00209   if (!i_min)
00210     return 0;
00211 
00212   for(i = i_min + 1; i <= get_rows(); i++)
00213   {
00214     if((at(i, pivot_col) > T(0)) && (at(i, 0) / at(i, pivot_col) < min) )
00215     {
00216       min = at(i, 0) / at(i, pivot_col);
00217       i_min = i;
00218     }
00219   }
00220 
00221   return i_min;
00222 }
00223 
00224 //*************************************************************************
00225 
00226 template <class T> int 
00227 simplex_table<T>::
  is_primal_feasible()
00228 {
00229   return !find_pivot_row();
00230 }
00231 
00232 //*************************************************************************
00233 
00234 template <class T> int 
00235 simplex_table<T>::
  is_dual_feasible()
00236 {
00237   return !find_pivot_col();
00238 }
00239 
00240 //*************************************************************************
00241 
00242 template <class T> void 
00243 simplex_table<T>::
  pivoting_col(index pivot_row, index pivot_col)
00244 {
00245   T pivot_item = -at(pivot_row, pivot_col);
00246 
00247   div_col(pivot_col, pivot_item);
00248 
00249   non_bas_var[pivot_col] = pivot_row;
00250 
00251   for(index j = 0; j <= get_cols(); j++)
00252     if(j != pivot_col)
00253       add_col(j, pivot_col, at(pivot_row, j));
00254 }
00255 
00256 //*************************************************************************
00257 
00258 template <class T> int 
00259 simplex_table<T>::
  primal_simplex_col()
00260 {
00261   index pivot_col;
00262   while(pivot_col = find_pivot_col())
00263   {
00264     index pivot_row;
00265     if(pivot_row = find_pivot_row(pivot_col))
00266       pivoting_col(pivot_row, pivot_col);
00267     else
00268       return 0;
00269   }
00270   return 1;
00271 }
00272 
00273 //*************************************************************************
00274 
00275 template <class T> int 
00276 simplex_table<T>::
  dual_simplex_col()
00277 {
00278   index pivot_row;
00279   while(pivot_row = find_pivot_row())
00280   {
00281     index pivot_col = find_pivot_col(pivot_row);
00282     if(pivot_col)
00283       pivoting_col(pivot_row, pivot_col);
00284     else
00285       return 0;
00286   }
00287   return 1;
00288 }
00289 
00290 //*************************************************************************
00291 
00292 template <class T> index simplex_table<T>::
00293   is_non_bas_var(index j)
00294 {
00295   for (index i = 1; i <= get_cols(); i++)
00296     if (non_bas_var[i] == j)
00297       return i;
00298   return 0;
00299 }
00300 
00301 //*************************************************************************
00302 
00303 template <class T> index 
00304 simplex_table<T>::
  find_generating_row()
00305 {
00306    for(index i = 0; i <= get_rows(); i++)
00307    {
00308      if (!is_integer(at(i, 0))) return i;
00309    }
00310    return -1;
00311 }
00312 
00313 //*************************************************************************
00314 
00315 template <class T> index 
00316 simplex_table<T>::
  find_generating_row_mip()
00317 {
00318    for(index i = 1; i <= k; i++)
00319    {
00320      if (!is_integer(at(i, 0))) return i;
00321    }
00322    return -1;
00323 }
00324 
00325 //*************************************************************************
00326 
00327 template <class T> int 
00328 simplex_table<T>::
  gomory1()
00329 {
00330   index generating_row;
00331 
00332   while((generating_row = find_generating_row()) != -1)
00333   {
00334 
00335     // old cut plain deleting
00336 
00337     if (old_cut_plane_deleting)
00338     {
00339       index i = init_rows + 1;
00340       while(i <= get_rows())
00341       {
00342         if (is_non_bas_var(i))
00343           i++;
00344         else
00345         {
00346           del_row(i);
00347           for(index j = 1; j <= get_cols(); j++)
00348             if (non_bas_var[j] > i)
00349               non_bas_var[j]--;
00350         }
00351       }
00352     }
00353 
00354     // cut constructing
00355 
00356     ins_row(get_rows() + 1);
00357 
00358     operator()(get_rows(), 0) =
00359       floor(at(generating_row, 0)) - at(generating_row, 0);
00360       // integer part
00361 
00362     for (index j = 1; j <= get_cols(); j++)
00363     {
00364       operator()(get_rows(), j) =
00365         floor(at(generating_row, j)) - at(generating_row, j);
00366     }
00367 
00368     cout << "\n after cutting: \n" << *this;
00369 
00370     // simplex method...
00371 
00372     if(!dual_simplex_col())
00373     {
00374       cout << "\n problem has no feasible solution \n" << *this;
00375       return 0;
00376     }
00377 
00378     cout << "\n after simplex method: \n" << *this;
00379   }
00380 
00381   cout << "problem is solved" << "\n" << "result matrix:" << *this;
00382   return 1;
00383 }
00384 
00385 //*************************************************************************
00386 
00387 template <class T> int 
00388 simplex_table<T>::
  gomory2()
00389 {
00390   index generating_row;
00391 
00392   while((generating_row = find_generating_row_mip()) != -1)
00393   {
00394 
00395     // old cut plain deleting
00396 
00397     if (old_cut_plane_deleting)
00398     {
00399       index i = init_rows + 1;
00400       while(i <= get_rows())
00401       {
00402         if (is_non_bas_var(i))
00403           i++;
00404         else
00405         {
00406           del_row(i);
00407           for(index j = 1; j <= get_cols(); j++)
00408             if (non_bas_var[j] > i)
00409               non_bas_var[j]--;
00410         }
00411       }
00412     }
00413 
00414     // cut constructing
00415 
00416     ins_row(get_rows() + 1);
00417 
00418     T f0 = at(generating_row, 0) - floor(at(generating_row, 0));
00419     operator()(get_rows(), 0) = 0-f0;
00420 
00421     for (index j = 1; j <= get_cols(); j++)
00422     {
00423       T f = at(generating_row, j) - floor(at(generating_row, j));
00424       if (non_bas_var[j] <= k)
00425       {
00426         if (f <= f0)
00427           operator()(get_rows(), j) = 0-f;
00428         else
00429           operator()(get_rows(), j) = f0 / (f0 - 1) * (1 - f);
00430       }
00431       else
00432       {
00433         if (at(generating_row, j) >= 0)
00434           operator()(get_rows(), j) = 0-at(generating_row, j);
00435         else
00436           operator()(get_rows(), j) = f0 / (1 - f0) * at(generating_row, j);
00437       }
00438     }
00439 
00440     cout << "\n after cutting: \n" << *this;
00441 
00442     // simplex method...
00443 
00444     if(!dual_simplex_col())
00445     {
00446       cout << "\n problem has no feasible solution \n" << *this;
00447       return 0;
00448     }
00449 
00450     cout << "\n after simplex method: \n" << *this;
00451   }
00452 
00453   cout << "problem is solved" << "\n" << "result matrix:" << *this;
00454   return 1;
00455 }
00456 
00457 #endif
00458 
00459 

Generated at Tue Jan 22 20:37:04 2002 for Arageli by doxygen1.2.9.1 written by Dimitri van Heesch, © 1997-2001