文档章节

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 FLA......

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

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

qq_36523667
01/09
0
0
C++ Unicode SBCS 函数对照表

原文链接:http://blog.csdn.net/augusdi/article/details/4399849

晨曦之光
2012/03/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(list......

Vermouth0
2016/05/14
82
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

(一)软件测试专题——之Linux常用命令篇01

本文永久更新地址:https://my.oschina.net/bysu/blog/1931063 【若要到岸,请摇船:开源中国 不最醉不龟归】 Linux的历史之类的很多书籍都习惯把它的今生来世,祖宗十八代都扒出来,美其名曰...

不最醉不龟归
20分钟前
3
0
蚂蚁金服Java开发三面

8月20号晚上8点进行了蚂蚁金服Java开发岗的第三面,下面开始: 自我介绍(要求从实践过程以及技术背景角度着重介绍) 实习经历,说说你在公司实习所做的事情,学到了什么 关于你们的交易平台...

edwardGe
27分钟前
7
0
TypeScript基础入门 - 函数 - this(三)

转载 TypeScript基础入门 - 函数 - this(三) 项目实践仓库 https://github.com/durban89/typescript_demo.gittag: 1.2.4 为了保证后面的学习演示需要安装下ts-node,这样后面的每个操作都能...

durban
37分钟前
0
0
Spark core基础

Spark RDD的五大特性 RDD是由一系列的Partition组成的,如果Spark计算的数据是在HDFS上那么partition个数是与block数一致(大多数情况) RDD是有一系列的依赖关系,有利于Spark计算的容错 RDD中每...

张泽立
45分钟前
0
0
如何搭建Keepalived+Nginx+Tomcat高可用负载均衡架构

一.概述 初期的互联网企业由于业务量较小,所以一般单机部署,实现单点访问即可满足业务的需求,这也是最简单的部署方式,但是随着业务的不断扩大,系统的访问量逐渐的上升,单机部署的模式已...

Java大蜗牛
59分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部