Embed Size (px)
DESCRIPTION
simulación de tiempos de repuesta en vehículos de atención en emergencias
Citation preview
1.1 Introducción
La preservación de la vida desde siempre ha sido un tema de bastante
importancia, desde la antigüedad se hacían operaciones con instrumentos
rudimentarios con tal de salvar una vida, tal fue el problema de que las personas
que requerían atención muchas veces no podían llegar a la ubicación de estos
profesionales médicos para poder ser atendidos, por tal razón se invento una
forma de transporte mediante un vehículo así nació la primera ambulancia que
contenía material necesario para extender la vida del paciente al menos hasta que
se pueda llegar al centro de atención.
Pero se presenta un problema en la actualidad la demora por los largos
recorridos embotellamientos y demás ha ocasionado que varias personas pierdan
la vida, para este motivo el presente trabajo tiene como objetivo diseñar un modelo
de simulación de tiempos por ambulancia para poder reducir asi el tiempo de
llegada en el centro de atención medico
1.1.1 Descripción del modelo
El modelo a desarrollar esta basada en la teoría programación lineal entera mixta.
El modelo a utilizar es el de problemas de rutas de vehículos, Con el cual se
puede estimar el tiempo de demora de los vehículos así tomar la mejor opción
para el transporte de heridos
1.1.2 Alcances
Los el modelo simulara los tiempos de acción en caso de ser necesarios para la
atención de las personas que requieran de este servicio
El modelo matemático se tomara tres tipos de vehículos los de atención, los de
urgencia y los de emergencia.
El sistema modelara tiempos para su mejor toma de decisión
1.1.3 Limites
Solo se trabaja con los límites de la ciudad de La Paz
Solo se trabaja con vehículos terrestres
Los vehículos tienen las mismas características (respecto a potencia, kilometraje
etc)
1.2 Objetivos
1.2.1 Objetivo general
Desarrollar un sistema de simulación logística para la asignación y/o despacho de
vehículos de emergencias médicas en la empresa “San Valentín”
1.2.2 Objetivos secundarios
Diseñar el sistema en base al modelo matemático para la simulación
Modelar todos los casos posibles de estados de los vehículos para el sistema
Desarrollar el sistema de simulación logística para la asignación y/o despacho de
vehículos
2 Marco teórico
2.1 Simulación
2.1.1 Definición
La simulación es el proceso de diseñar un modelo de un sistema real y llevar a
término experiencias con él, con la finalidad de comprender el comportamiento del
sistema o evaluar nuevas estrategias -dentro de los límites impuestos por un cierto
criterio o un conjunto de ellos para el funcionamiento del sistema
2.1.2 Características
Un modelo de simulación requiere de las siguientes características para ser fiable
Que sea completo
Adaptabilidad
Credibilidad
Simplicidad (menor número de parámetros)
Factible tanto en Información como en recursos
Económico
2.1.3 Aplicaciones
Las aplicaciones de la simulación se extiende por varias áreas tales como
2.1.3.1 Simulación por computadora
La simulación por computadora se ha convertido en una parte útil del modelado de
muchos sistemas naturales en física, química y biología, y sistemas humanos
como la economía y las ciencias sociales (sociología computacional),3 así como
en dirigir para ganar la penetración (profundidad) su comportamiento cambiará
cada simulación según el conjunto de parámetros iniciales supuestos por el
entorno. Las simulaciones por computadora son a menudo consideradas seres
humanos fuera de un loop de simulación.
Tradicionalmente, el modelado formal de sistemas ha sido a través de un modelo
matemático, que intenta encontrar soluciones analíticas a problemas que permiten
la predicción del comportamiento de un sistema de un conjunto de parámetros y
condiciones iniciales. La simulación por computadora es frecuentemente usada
como un accesorio para, o sustitución de, sistemas de modelado para los cuales
las soluciones analíticas de forma cerrada simple no son posibles. Ahí se
encuentran muchos tipos diferentes de simulación por computadora, la
característica común que todas ellas comparten es el intento por generar una
muestra de escenarios representativos para un modelo en que una enumeración
completa de todos los estados posibles serían prohibitivos o imposibles. Varios
paquetes de software existen para modelar por computadora, como Vensim, Stella
o Powerim, y así la simulación se hace sin gran esfuerzo
Es cada vez más común escuchar acerca de simulaciones a muchas clases
designadas como "ambientes sintéticos". Esta etiqueta ha sido adoptada al
ampliar la definición de "simulación", que abarca virtualmente cualquier
representación computarizada.
2.1.3.2 Simulación en informática
En informática la simulación tiene todavía mayor significado especializado: Alan
Turing usó el témino "simulación" para referirse a lo que pasa cuando una
computadora digital corre una tabla de estado (corre un programa) que describe
las transiciones de estado, las entradas y salidas de una máquina sujeta a
discreto-estado. La simulación computarizada de una máquina sujeta.
En programación, un simulador es a menudo usado para ejecutar un programa
que tiene que correr en ciertos tipos de inconvenientes de computadora o en un
riguroso controlador de prueba de ambiente. Por ejemplo, los simuladores son
frecuentemente usados para depurar un microprograma (microcódigo) o algunas
veces programas de aplicación comercial. Dado que, la operación de
computadoras es simulada, toda la información acerca de la operación de
computadoras es directamente disponible al programador, y la velocidad y
ejecución pueda variar a voluntad.
Los simuladores pueden ser usados para interpretar la ingeniería de seguridad o
la prueba de diseño de lógica VLSI, antes de que sean construidos. En informática
teórica el término "simulación" representa una relación entre los sistemas de
transición de estado. Esto es usado en el estudio de la semántica operacional.
En el área de las ciencias son de gran ayuda ya que los estudiantes relacionan
conceptos abstractos con reales (el choque de moléculas) y también ayuda en el
sentido de los recursos ya que solo se tiene que disponer con un par de
computadores y no con todo el aparataje de un laboratorio entero.
2.1.3.3 Simulación en la preparación
La simulación es usada en el entrenamiento o preparación tanto del personal civil
como militar; esto sucede cuando es prohibitivamente caro o simplemente muy
peligroso para permitirle usar equipo real a un aprendiz en el mundo real. En esta
última situación ellos aprenderán valiosas lecciones en un ambiente virtual seguro.
La conveniencia es permitir errores durante el entrenamiento para un sistema
crítico de seguridad.
El entrenamiento simulado típicamente viene en tres categorías:
Simulación de "Vida", es cuando las personas reales usan equipo simulado en el
mundo real.
Simulación "Virtual", es cuando las personas reales usan equipo simulado en
mundos simulados o ambientes virtuales.
Simulación "Constructiva", es cuando personas simuladas, usan equipo simulado,
en ambientes simulados.
2.1.3.4 Simulación en la educación
Este tipo de simulación es un tanto parecida a la de entrenamiento o preparación.
Ellas se enfocan en tareas específicas. En el pasado los videos eran usados por
maestros y para educar alumnos a observar, solucionar problemas y jugar un rol;
sin embargo se ha visto desplazada por la simulación, puesto que esta incluye
viñetas narrativas animadas, son videos de caricaturas hipotéticas e historias
basadas en la realidad, envolviendo a la clase en la enseñanza y aprendizaje.
También se usa para evaluar el aprendizaje, resolver problemas de habilidades y
disposición de los niños, y el servicio de los profesores.
2.1.3.5 Simulación en las ciencias naturales
Los experimentos basados en técnicas como la espectroscopia de RMN proveen
datos detallados sobre el comportamiento de la materia. Sin embargo, para
interpretar estos experimentos y para obtener una resolución mayor en espacio y
tiempo, tenemos que recurrir a modelos teóricos. La resolución analítica de estos
modelos es imposible para la mayoría de los sistemas de interés práctico. Por ello,
es necesario recurrir a la resolución numérica de estos modelos en forma de
simulaciones. Una simulación busca recrear los elementos que se consideran
importantes en la reproducción de un fenómeno observado empíricamente.
Ejemplos importantes son la dinámica molecular y la química computacional,
ambas utilizadas ampliamente para estudiar el plegamiento de proteínas en la
biofísica y las propiedades mecánicas de polímeros artificiales en la ciencia de
materiales.
2.1.3.6 Simulación médica
Este tipo de simulación incrementa cada vez más su desarrollo y se está
desplegando cada vez más para enseñar procedimientos terapéuticos y de
diagnóstico así como conceptos y la toma de decisión médica al personal en las
profesiones médicas. Estos simuladores se han estado desarrollando para el
entrenamiento en una gama de procedimientos básicos como la transfusión de
sangre, una cirugía laparoscópica, cuidados traumatológicos auscultación
pulmonar y cardiaca, etc.
2.2 Área de investigación
2.2.1 Definición
2.2.1.1 Atención de emergencias
Los Servicios de Atención Medica Urgente son mejor conocidos en el mundo bajo
su acrónimo internacional SAMU. Son Centros regionales de Regulación Medico-
Sanitaria de las Urgencias exclusivamente Regulación Médico Sanitaria de las
Urgencias. Muchos son accesibles para el Público a través de un número nacional
exclusivo o a través de los Números de Alerta Generales (Policía ,112, 911). Están
conectados con todos los recursos de la atención medica y de las ambulancias.
Un Médico Regulador esta continuamente encargado de clasificar las Urgencias y
de decidir de la mejor solución para los pacientes. El Sistema Integrado de
Urgencias Médicas que regulan y mismo las Ambulancias que tienen autorización
de llevar su siglo regional
2.2.2 Características
La empresa actual que utiliza de unidades de transporte de heridos(ambulancias)
realiza servicios prestados con vehículos médicos en cuanto a tres tipos de
llamadas, denominadas en orden de prioridad: Emergencia (urgente, síntomas con
amenaza a la vida), Urgencia (urgente, pero no existe amenaza a la vida) y
Consultas (no urgentes). Dispone de una flota heterogénea de tres tipos de
vehículos clasificados en vehículo de consulta (VC), Transporte de Ambulancia
Básica (TAB) y Transporte de Ambulancia Medicalizada (TAM). Los vehículos de
tipo TAM pueden atender cualquier tipo de llamada, los de tipo TAB no pueden
atender emergencias y los VC solo pueden atender consultas
2.3 Formulas incluidas en el modelo
En las últimas décadas, el uso de modelos de programación lineal entera mixta
para resolver problemas de Optimización Combinatoria se ha incrementado
enormemente. Mediante un problema de programación lineal entera mixta se
pueden modelar situaciones donde se debe minimizar una función lineal sujeta a
un conjunto de restricciones, también lineales, donde algunas, o todas, las
variables solo pueden tomar valores enteros. Este es el caso del Problema del
Viajante de Comercio, problemas en redes, problemas de asignación de recursos,
problemas de teoría de grafos, y muchísimos otros problemas de optimización
combinatoria provenientes de una gran cantidad de disciplinas
Un caso es El problema de rutas de vehículos
2.3.1 El problema de rutas de vehículos o Vehicle Routing Problem (VRP)
En este caso disponemos de varios vehículos que deben visitar varias poblaciones
y varias estacio-nes de donde parten y terminan los recorridos. Si consideramos
la capacidad (C) de los vehículos (m), que partiendo y volviendo de una única
estación deben distribuir o recoger (nuestro caso) una demanda de mercancía (d)
entonces estamos en un caso particular llamadoCapacited Vehicle Routing
Problem (CVRP). La función a minimizar sigue siendo el coste del recorrido y este
coste se puede interpretar como tiempo, distancia, coste económico, etc.
Cada población tiene asociada una determinada demanda (d) que debe ser
satisfecha por la flota de vehículos. En el sentido más simplista del problema, los
vehículos empiezan y terminan su recorrido en un mismo punto con capacidad
ilimitada, no obstante, los vehículos tienen capacidades limitadas y pueden ser
diferentes así como un coste fijo relacionado con su disponibilidad, de manera que
se prime el maximizar cada vehículo al total de su capacidad frente al uso de un
número mayor de vehículos.
La formulación del problema, según Toth y Vigo sería:
Minimizar
Siendo n el número de poblaciones y m el número de vehículos.
Sujeto a las siguientes restricciones:
No pueden salir más vehículos de los que hay:
El número de vehículos que salen del punto 1 es el mismo que el número que
vuelven:
Tenemos que respetar la capacidad máxima y evitar subciclos:
Siendo ui y uj variables enteras auxiliares y Q la demanda total.
2.3.2 Forma de resolución
Métodos heurísticos
Algoritmo de ahorro de tiempo Lo que busca es mezclar rutas con un criterio de
pegado entre ellas,
Clarke y Wright (1964), a partir de dos rutas estas se pegan formando una única
ruta registrando los ahorros de tiempo resultantes, como se ilustra
Códigos de ayuda
ackage org.metavrp.VRP;import java.util.ArrayList;import org.metavrp.GA.support.*;import org.metavrp.GA.*;//import java.util.logging.Level;//import java.util.logging.Logger;/** * * @author David Pinheiro */public class VRPMain { /** * @param args the command line arguments */ public static void main(String[] args) { int popSize=1000; int nrVehicles=1; float elitism=0.01f; float mutationProb=0.1f; float crossoverProb=0.8f; int generations=500; String fileName = "c:/vrp-tsp/dm171.txt"; CostMatrix costMatrix = new CostMatrix(fileName, false); // Create the Gene List GeneList geneList = generateGeneList(nrVehicles, costMatrix.size-1); GAParameters params = new GAParameters(popSize, elitism, mutationProb, crossoverProb, generations); VRPGARun run = new VRPGARun(params, geneList, costMatrix); // Start in a new thread Thread vrpThread = new Thread(run, "metaVRP"); vrpThread.start(); } // Given some number of nodes and of vehicles, creates a simple list of genes. // This is a very simplified (and useless?) constructor, as all the vehicles start from node 0 public static GeneList generateGeneList(int nrVehicles, int nrNodes){ // Generate the customers array ArrayList<Customer> customers = new ArrayList<Customer>(nrNodes); // Add the customers for (int i=1;i<nrNodes+1;i++){ customers.add(new Customer(i,i)); } // Generate the vehicles array ArrayList<Vehicle> vehicles = new ArrayList<Vehicle>(nrVehicles);
// Add the vehicles // All of them start from the first node (node 0) for (int i=0;i<nrVehicles;i++){ vehicles.add(new Vehicle(-1-i,0)); } return new GeneList(customers, vehicles); }}
packag
e Vrp;
import java.util.LinkedList;
import java.util.Scanner;
import org.jgap.*;
import org.jgap.impl.*;
public class Vrp {
private static final int MAX_EVOLUTIONS = 5000;
public static void Vrp() throws Exception{
Configuration conf = new DefaultConfiguration();
conf.setPreservFittestIndividual(true);
System.out.println("------VRP-----");
System.out.println("Elige el archivo con el problema vrp: ");
System.out.println("0) test [10 destinos]");
System.out.println("1) 45 destinos");
System.out.println("2) 60 destinos");
System.out.println("");
int seleccion, camiones;
Scanner scanIn = new Scanner(System.in);
VrpConfiguration vrpconf = null;
seleccion = scanIn.nextInt();
System.out.println("Coloca el numero de camiones: ");
camiones = scanIn.nextInt();
if (seleccion == 0)
{
vrpconf = new VrpConfiguration();
}
else if (seleccion == 1)
{
vrpconf = new VrpConfiguration("Extras/A-n45-k6-in.txt",
camiones);
}
else if (seleccion == 2)
{
vrpconf = new VrpConfiguration("Extras/A-n60-k0-in.txt",
camiones);
}
else
{
vrpconf = new VrpConfiguration();
}
vrpconf.print();
FitnessFunction myFunc = new VrpFitnessFunc(vrpconf);
conf.setFitnessFunction(myFunc);
Gene[] sampleGenes = new Gene[vrpconf.GRAPH_DIMENSION];
/*
* Iniciar los Genes en sus valores minimos y máximos
*/
for(int i=0; i<vrpconf.GRAPH_DIMENSION; i++){
sampleGenes[i] = new IntegerGene(conf, 0,
(vrpconf.VEHICLE_NUMBER-1));
}
IChromosome sampleChromosome = new Chromosome(conf,
sampleGenes);
conf.setSampleChromosome(sampleChromosome);
conf.setPopulationSize(60);
Genotype population;
population = Genotype.randomInitialGenotype(conf);
long startTime = System.currentTimeMillis();
for (int i = 0; i < MAX_EVOLUTIONS; i++) {
if(i%50 == 0)
System.out.print(".");
if(i%5000 == 0)
System.out.println("");
if (!uniqueChromosomes(population.getPopulation())) {
throw new RuntimeException("Generación inválida en
la evolucion: " + i);
}
population.evolve();
}
long endTime = System.currentTimeMillis();
System.out.println("");
System.out.println("Tiempo total de la evolución: " +
( endTime - startTime) + " ms");
System.out.println("Numero total de evoluciónes: " +
MAX_EVOLUTIONS);
IChromosome bestSolutionSoFar =
population.getFittestChromosome();
double v1 = bestSolutionSoFar.getFitnessValue();
System.out.println("La mejor solución fitness fue: " + v1);
bestSolutionSoFar.setFitnessValueDirectly(-1);
System.out.println("Resultado: ");
for (int i = 0; i < vrpconf.GRAPH_DIMENSION; i++) {
System.out.println(i +". " +
VrpFitnessFunc.getNumberAtGene(bestSolutionSoFar, i) );
}
Double distance = 0.0;
Double distancep= 0.0;
LinkedList routes;
for(int i = 0; i<vrpconf.VEHICLE_NUMBER;i++){
distancep = VrpFitnessFunc.getDistance(i,
bestSolutionSoFar, vrpconf);
routes = VrpFitnessFunc.getPositions(i,
bestSolutionSoFar, vrpconf);
System.out.print("Ruta #" + i + " :");
while(!routes.isEmpty()){
int pos = ((Integer) routes.pop()).intValue();
System.out.print(pos + ", ");
}
System.out.println();
System.out.println("\t La distancia de la ruta es:
"+distancep);
distance += distancep;
}
System.out.println("La mejor distancia fue: " + distance);
System.out.println();
}
public static boolean uniqueChromosomes(Population a_pop) {
for(int i=0;i<a_pop.size()-1;i++) {
IChromosome c = a_pop.getChromosome(i);
for(int j=i+1;j<a_pop.size();j++) {
IChromosome c2 =a_pop.getChromosome(j);
if (c == c2) {
return false;
}
}
}
return true;
}
public static void main(String[] args) throws Exception {
Vrp();
}
}
/************************************************************************* * Compilation: javac Simplex.java * Execution: java Simplex * * Given an M-by-N matrix A, an M-length vector b, and an * N-length vector c, solve the LP { max cx : Ax <= b, x >= 0 }. * Assumes that b >= 0 so that x = 0 is a basic feasible solution. * * Creates an (M+1)-by-(N+M+1) simplex tableaux with the * RHS in column M+N, the objective function in row M, and * slack variables in columns M through M+N-1. * *************************************************************************/
public class Simplex { private static final double EPSILON = 1.0E-10; private double[][] a; // tableaux private int M; // number of constraints private int N; // number of original variables
private int[] basis; // basis[i] = basic variable corresponding to row i // only needed to print out solution, not book
// sets up the simplex tableaux public Simplex(double[][] A, double[] b, double[] c) { M = b.length; N = c.length; a = new double[M+1][N+M+1]; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) a[i][j] = A[i][j]; for (int i = 0; i < M; i++) a[i][N+i] = 1.0; for (int j = 0; j < N; j++) a[M][j] = c[j]; for (int i = 0; i < M; i++) a[i][M+N] = b[i];
basis = new int[M]; for (int i = 0; i < M; i++) basis[i] = N + i;
solve();
// check optimality conditions assert check(A, b, c); }
// run simplex algorithm starting from initial BFS private void solve() { while (true) {
// find entering column q int q = bland(); if (q == -1) break; // optimal
// find leaving row p int p = minRatioRule(q); if (p == -1) throw new ArithmeticException("Linear program is unbounded");
// pivot pivot(p, q);
// update basis basis[p] = q; } }
// lowest index of a non-basic column with a positive cost private int bland() { for (int j = 0; j < M + N; j++) if (a[M][j] > 0) return j; return -1; // optimal }
// index of a non-basic column with most positive cost private int dantzig() { int q = 0; for (int j = 1; j < M + N; j++) if (a[M][j] > a[M][q]) q = j;
if (a[M][q] <= 0) return -1; // optimal else return q; }
// find row p using min ratio rule (-1 if no such row) private int minRatioRule(int q) { int p = -1; for (int i = 0; i < M; i++) { if (a[i][q] <= 0) continue; else if (p == -1) p = i; else if ((a[i][M+N] / a[i][q]) < (a[p][M+N] / a[p][q])) p = i; } return p; }
// pivot on entry (p, q) using Gauss-Jordan elimination private void pivot(int p, int q) {
// everything but row p and column q for (int i = 0; i <= M; i++) for (int j = 0; j <= M + N; j++) if (i != p && j != q) a[i][j] -= a[p][j] * a[i][q] / a[p][q];
// zero out column q for (int i = 0; i <= M; i++) if (i != p) a[i][q] = 0.0;
// scale row p for (int j = 0; j <= M + N; j++) if (j != q) a[p][j] /= a[p][q]; a[p][q] = 1.0; }
// return optimal objective value public double value() { return -a[M][M+N]; }
// return primal solution vector public double[] primal() { double[] x = new double[N]; for (int i = 0; i < M; i++) if (basis[i] < N) x[basis[i]] = a[i][M+N]; return x; }
// return dual solution vector public double[] dual() { double[] y = new double[M]; for (int i = 0; i < M; i++) y[i] = -a[M][N+i]; return y; }
// is the solution primal feasible? private boolean isPrimalFeasible(double[][] A, double[] b) { double[] x = primal();
// check that x >= 0 for (int j = 0; j < x.length; j++) { if (x[j] < 0.0) { StdOut.println("x[" + j + "] = " + x[j] + " is negative"); return false; } }
// check that Ax <= b for (int i = 0; i < M; i++) { double sum = 0.0;
for (int j = 0; j < N; j++) { sum += A[i][j] * x[j]; } if (sum > b[i] + EPSILON) { StdOut.println("not primal feasible"); StdOut.println("b[" + i + "] = " + b[i] + ", sum = " + sum); return false; } } return true; }
// is the solution dual feasible? private boolean isDualFeasible(double[][] A, double[] c) { double[] y = dual();
// check that y >= 0 for (int i = 0; i < y.length; i++) { if (y[i] < 0.0) { StdOut.println("y[" + i + "] = " + y[i] + " is negative"); return false; } }
// check that yA >= c for (int j = 0; j < N; j++) { double sum = 0.0; for (int i = 0; i < M; i++) { sum += A[i][j] * y[i]; } if (sum < c[j] - EPSILON) { StdOut.println("not dual feasible"); StdOut.println("c[" + j + "] = " + c[j] + ", sum = " + sum); return false; } } return true; }
// check that optimal value = cx = yb private boolean isOptimal(double[] b, double[] c) { double[] x = primal(); double[] y = dual(); double value = value();
// check that value = cx = yb double value1 = 0.0; for (int j = 0; j < x.length; j++) value1 += c[j] * x[j]; double value2 = 0.0; for (int i = 0; i < y.length; i++) value2 += y[i] * b[i]; if (Math.abs(value - value1) > EPSILON || Math.abs(value - value2) > EPSILON) {
StdOut.println("value = " + value + ", cx = " + value1 + ", yb = " + value2); return false; }
return true; }
private boolean check(double[][]A, double[] b, double[] c) { return isPrimalFeasible(A, b) && isDualFeasible(A, c) && isOptimal(b, c); }
// print tableaux public void show() { StdOut.println("M = " + M); StdOut.println("N = " + N); for (int i = 0; i <= M; i++) { for (int j = 0; j <= M + N; j++) { StdOut.printf("%7.2f ", a[i][j]); } StdOut.println(); } StdOut.println("value = " + value()); for (int i = 0; i < M; i++) if (basis[i] < N) StdOut.println("x_" + basis[i] + " = " + a[i][M+N]); StdOut.println(); }
public static void test(double[][] A, double[] b, double[] c) { Simplex lp = new Simplex(A, b, c); StdOut.println("value = " + lp.value()); double[] x = lp.primal(); for (int i = 0; i < x.length; i++) StdOut.println("x[" + i + "] = " + x[i]); double[] y = lp.dual(); for (int j = 0; j < y.length; j++) StdOut.println("y[" + j + "] = " + y[j]); }
public static void test1() { double[][] A = { { -1, 1, 0 }, { 1, 4, 0 }, { 2, 1, 0 }, { 3, -4, 0 }, { 0, 0, 1 }, }; double[] c = { 1, 1, 1 }; double[] b = { 5, 45, 27, 24, 4 }; test(A, b, c); }
// x0 = 12, x1 = 28, opt = 800
public static void test2() { double[] c = { 13.0, 23.0 }; double[] b = { 480.0, 160.0, 1190.0 }; double[][] A = { { 5.0, 15.0 }, { 4.0, 4.0 }, { 35.0, 20.0 }, }; test(A, b, c); }
// unbounded public static void test3() { double[] c = { 2.0, 3.0, -1.0, -12.0 }; double[] b = { 3.0, 2.0 }; double[][] A = { { -2.0, -9.0, 1.0, 9.0 }, { 1.0, 1.0, -1.0, -2.0 }, }; test(A, b, c); }
// degenerate - cycles if you choose most positive objective function coefficient public static void test4() { double[] c = { 10.0, -57.0, -9.0, -24.0 }; double[] b = { 0.0, 0.0, 1.0 }; double[][] A = { { 0.5, -5.5, -2.5, 9.0 }, { 0.5, -1.5, -0.5, 1.0 }, { 1.0, 0.0, 0.0, 0.0 }, }; test(A, b, c); }
// test client public static void main(String[] args) {
try { test1(); } catch (ArithmeticException e) { e.printStackTrace(); } StdOut.println("--------------------------------");
try { test2(); } catch (ArithmeticException e) { e.printStackTrace(); } StdOut.println("--------------------------------");
try { test3(); } catch (ArithmeticException e) { e.printStackTrace(); } StdOut.println("--------------------------------");
try { test4(); } catch (ArithmeticException e) { e.printStackTrace(); } StdOut.println("--------------------------------");
int M = Integer.parseInt(args[0]); int N = Integer.parseInt(args[1]); double[] c = new double[N]; double[] b = new double[M]; double[][] A = new double[M][N]; for (int j = 0; j < N; j++) c[j] = StdRandom.uniform(1000); for (int i = 0; i < M; i++) b[i] = StdRandom.uniform(1000); for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) A[i][j] = StdRandom.uniform(100); Simplex lp = new Simplex(A, b, c); StdOut.println(lp.value()); }
}
Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. Last updated: Thu Apr 11 19:20:36 EDT 2013.
Introducción.
Los programas matemáticos implican a un conjunto de variables relacionadas por un conjunto de ecuaciones matemáticas (restricciones) y una función objetivo que contiene a las variables y que debe maximizarse respetando las restricciones dadas, de aquí que si todas las ecuaciones en juego son simples combinaciones lineales de las variables, se tenga un programa lineal.
Para resolver este tipo de ecuaciones, o programas lineales se emplea el método simplex el cual consiste en una región convexa definida por intersecciones de semiplanos, este método consiste en agregar variables de holgura a cada un de las ecuaciones lineales con la finalidad de convertirlas en igualdades, luego se hace una tabla con los coeficientes de estas igualdades incluyendo a la función objetivo a la cual se le cambia el signo, formando así un matriz de coeficientes.
De esta matriz se selecciona un elemento [p][q], después se multiplica la p-ésima fila por un escalar apropiado y se suma a todas las filas restantes para llenar la q-esima columna de ceros excepto el elemento de la fila q que se pone a 1y así sucesivamente hasta que se llega a una matriz que tiene en su diagonal principal solamente 1 maximizando así la función objetivo.
Lo siguiente es un algoritmo que nos permite implementar el método simplex en donde primero se toman los valores de los coeficientes, se crea la matriz se obtienen la columna del pivote y posteriormente la fila, se guardan los elementos se transforman y se imprimen para finalizar liberando el espacio de las variables.
Algoritmo en C del Método Simplex.
int main ( ) { unsigned n,e,*x; float *c,**a,*h,*v; unsigned i,j,bi,bj;
Toma de datos.
printf ("Num. var.: "); scanf ("%u",&n); printf ("Num. inec.: "); scanf ("%u",&e); c = calloc ( n+1, sizeof( float)); a = calloc ( e+1, sizeof( float*)); x = calloc ( e+1, sizeof( unsigned)); h = calloc ( n+1, sizeof( float)); v = calloc ( e+1, sizeof( float)); for ( i=0;i<n;i++) { printf ("Coef. x(%u) en la ec. del Maximo:",i+1); scanf ("%f",&c[i]); } for ( j=0;j<e;j++) { a[j] = calloc ( n+1, sizeof(float)); for ( i=0;i<n;i++) { printf ("Coef. x(%u) en la %u ec.:",i+1,j+1); scanf ("%f",&a[j][i]); } printf ("Term.Indep. de la %u ec.:",j+1); scanf ("%f",&a[j][n]); printf ("Subindice de variable aux. de la inecuacion h(i)"); scanf ("%u",&x[j]); x[j]--; }
Preparación de la matriz de datos.
for ( i=0; i<=n;i++ ){ a[e][i]=-c[i]; for ( j=0;j<e;j++){ a[e][i]+=a[j][i]*c[x[j]]; }
} for (i=0; i< n; i++ ){ printf ("c(%u)= %7.2f\n", i+1,c[i]); }
Obtención de la columna del elemento pivote.
bi=1; for ( i=0;i<n;i++){ if ( a[e][i]< a[e][bi] ) bi=i; } if ( a[e][bi]>=0 ) break;
Obtención de la fila del elemento pivote.
bj=1; for ( j=0;j<e;j++){ if ( a[j][n]*a[bj][bi] < a[bj][n]*a[j][bi] ) bj=j; } printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); for ( j=0; j< e; j++){ printf ("| x%u | %7.2f | ",x[j]+1,a[j][n] ); for ( i=0; i<n; i++ ){ if ((i==bi)&&(j==bj)) { printf ("%7.2f*",a[j][i] ); } else { printf ("%7.2f ",a[j][i] ); } } printf("|\n"); } printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); printf (" | %7.2f | ",a[e][n] ); for ( i=0; i<n; i++ ){ printf ("%7.2f ",a[e][i] ); } printf("|\n\n");
Guardar los datos de la fila y columna.
for (i=0;i<=n;i++ ){ h[i]=a[bj][i]; } for ( j=0;j<=e;j++ ){ v[j]=a[j][bi]; } for (i=0;i<=n;i++ ){ for ( j=0;j<=e;j++ ){ a[j][i] -= h[i]*v[j]/h[bi]; } } for (i=0;i<=n;i++ ){ a[bj][i]=h[i]/v[bj]; } x[bj]= bi; }
Se muestra la solución.
printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); for ( j=0; j< e; j++){ printf ("| x%u | %7.2f | ",x[j]+1,a[j][n] ); for ( i=0; i<n; i++ ){ printf ("%7.2f ",a[j][i] ); } printf("|\n"); }printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); printf (" | %7.2f | ",a[e][n] ); for ( i=0; i<n; i++ ){ printf ("%7.2f ",a[e][i] ); } printf("|\n\n"); printf ("\nSolucion:\n"); for ( j=0; j<e; j++){ printf ("x%u=%7.2f\n",x[j]+1,a[j][n]); }
Se libera el espacio de variables.
for ( j=0; j<=e; j++) free(a[j]); free(c); free(a); free(x); free(h); free(v); return 0;}
