00001
00002
00003
00004
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
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
00355
00356 ins_row(get_rows() + 1);
00357
00358 operator()(get_rows(), 0) =
00359 floor(at(generating_row, 0)) - at(generating_row, 0);
00360
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
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
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
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
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