文档章节

L P

ludlows
 ludlows
发布于 2014/10/07 22:55
字数 238
阅读 6
收藏 0

 

# solves *bounded* LPs of the form:
        # max cx
        # sub to: Ax <= b
from sympy import *
from itertools import combinations
        # enumerates all the vertices of {x | Ax <= b}
def enumeratevertices(A, b):
    m, n = A.rows, A.cols     
    for rowlist in combinations(range(m), n):
        Ap = A.extract(rowlist, range(n))
        bp = b.extract(rowlist, [0])
        if Ap.det() != 0:
            xp = Ap.LUsolve(bp)
            d = A * xp - b
            feasible = True
            for i in range(m):
                if d[i] > 0:
                    feasible = False
            if feasible:
                yield xp       
        # finds the optimum using vertex enumeration
def findoptimum(A, b, c):
    m, n = A.rows, A.cols
    bestvalue, bestvertex = None, None
    for vertex in enumeratevertices(A, b):
        if bestvalue is None or (vertex.T*c)[0] > bestvalue:
            bestvalue = (vertex.T * c)[0]
            bestvertex = vertex
    return bestvertex
def solve(A, b, c):
    x = findoptimum(A, b, c)
    if not x:
        print 'LP is infeasible'
    else:
        print 'Vertex', x.T, 'is optimal'
        print 'Optimal value is', c.T*x
if __name__ == '__main__':
    A = Matrix([[-10,  -6, -9, -10],
                [  8,  -6, -5,  -5],
                [ -7,  -1, -9,   3],
                [ -1,  -4,  5,  10],
                [  1,   2,  0,  10],
                [  2,  -9,  3,  -8],
                [ -8,  -1, -8,   1],
                [  7, -10,  4,  -4],
                [-10,   2,  5,   8],
                [ -7,   9,  4,  -4],
                [ -1,   0,  0,   0],
                [  0,  -1,  0,   0],
                [  0,   0, -1,   0],
                [  0,   0,  0,  -1]])
    b = Matrix([9, 7, 3, 4, 8, 0, 3, 2, 4, 8, 0, 0, 0, 0])
    c = Matrix([2, -2, -3, 8])
    solve(A, b, c)

© 著作权归作者所有

共有 人打赏支持
ludlows
粉丝 0
博文 15
码字总数 4195
作品 0
海淀
程序员
私信 提问
不知道程序哪里出问题了,好像是重复定义,希望大家指点一下

#include"stdio.h" #include"math.h" #include"time.h" #include"stdlib.h" #include"ctype.h" #include"string.h" #include"io.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FL......

---BearWolf
2013/11/20
83
0
C++单向链表及操作

(由于以前c++没认真学,所以画了几张图,站在内存的角度理解下,马上就搞明白了) typedef int ElemType; typedef struct Node{ ElemType data; struct Node *next; }Node, *LinkedList; L...

qq_36523667
01/09
0
0
数据结构第4-2讲双向链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢? 可以给每个元素附加一个指针域,指向下一个元素的存储位置。这种链表称为...

rainchxy
2017/11/21
0
0
按字典序词频统计 最后总会出现一下莫名的段错误 求大神指点!

#include #include #include #include #define MAXSIZE 20 typedef struct node{ int count; char s[MAXSIZE]; struct node *next; }list,*linkP; FILE *fp; linkP L = (linkP)malloc(sizeof......

Vermouth0
2016/05/14
109
0
关于单链表的一个问题

程序不知道哪里出错,一运行就崩溃,求助? #include"stdio.h" #include"stdlib.h" #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可执行 #defin......

ExtreU
2014/10/09
363
5

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot + Mybatis 配置多数据源(Srping boot 二)

前置条件,你已经配置好spring boot+mybatis,可以参考之前的博客 实现逻辑通过注解+aop切面编程来动态更新datasource 第一步,配置多个DataSource server: port: 8080freezing: ...

小海bug
2分钟前
0
0
连续潜在变量---概率PCA

最大似然PCA 用于PCA的EM算法 贝叶斯PCA 因子分解

中国龙-扬科
8分钟前
0
0
Mac 安装redis 及 redis desktop manager

1.安装redis 1.1 下载地址: http://download.redis.io/releases/ 1.2 本地新建个redis文件夹 1.3 切换到redis 安装下:cd /Users/用户名/Documents/redis/redis-3.2.5 1.4 make install 1.5......

qimh
13分钟前
0
0
Caffe(二)-Python-自定义网络

这里我们用一个例子先来体验一下 首先定义一下我们的环境变量 $PYTHONPATH,我这儿是Windows开发环境,至于Windows Caffe怎么编译由读者自己下去搞定 我使用的控制台是 Windows PowerShell 添...

Pulsar-V
57分钟前
10
0
ActiveMQ从入门到精通(二)之可靠性机制

ActiveMQ的可靠性机制 缘由( 确认JMS消息) 只要消息被确认之后,才认为消息被成功消费了。消息的成功消费包括三个阶段:客户端接收消息、客户端处理消息以及客户端确认消息。在事务性会话中...

一看就喷亏的小猿
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部