OKlibrary  0.2.1.6
LinearProgramming.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 18.7.2008 (Swansea) */
00002 /* Copyright 2008 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/TermSystems/Lisp/Conversions.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00024 
00025 
00026 /* ******************************************
00027    * Solving systems of linear inequalities *
00028    ******************************************
00029 */
00030 
00031 oklib_plain_include(simplex);
00032 
00033 /* Find some solution for A * x >= 0, where x_i >= 1 for i in pv,
00034    x_i <= -1 for i in nv, and x_i = 0 for i in zv.
00035    Returns "false" if system in unsolvable, and otherwise a
00036    solution vector x.
00037  */
00038 solve_lineq(A,pv,nv,zv) := block(
00039  [S, h : sm2hm({}), n : matrix_size(A)[2]],
00040   if n = 0 then return([]),
00041   S : minimize_lp(0,append(translate_matrix_ineq(A),
00042         map(interprete_poscond,pv), 
00043         map(interprete_negcond,nv), 
00044         map(interprete_zerocond,zv))), 
00045   if S = "Problem not feasible!" then return(false),
00046   S : second(S),
00047   for eq in S do set_hm(h,sconcat(lhs(eq)),rhs(eq)),
00048   return(
00049     map(lambda([x],if x=false then 0 else x),
00050         create_list(ev_hm(h,sconcat(special_symbol,i)),i,1,n))))$
00051 
00052