其中x是一个n维向量,也称决策变量;X是一个集合, 可以简单区域,也可以用一系列的等式和不等式甚至其 他形式表示,称为可行集。
1, 吉尼斯世界纪录; 2,总理的政府工作报告;
3,公司的领导的核心工作; 4,如何使用好自己的钱;
5,树木的生长问题; 6,群狼的捕猎计划;
7,行星的运行轨道; 8,原子的内部结构。
根据问题的结构,可以进行下面的一些分类
(1)线性规划:目标函数和约束是线性的
(2)非线性规划:目标函数或约束是非线性的
(3)整数规划:决策变量是离散的,只能取整数值
(4)多目标规划:目标函数有多个
线性规划:最简单、最广泛使用。George B. Dantzig, 1947年线性规划单纯型算法
非线性规划:更多的应用背景。1951年Kuhn和Tucker,最优性条件。
整数规划:最富于挑战、回归本源。 1958年R.E.戈莫里,割平面法
多目标规划:人性多样化要求。1896年法国经济学家 V.帕累托提出多样化思想。
一家现代化兔子饲养场饲养一种兔子。根据兔子在不同时期的体重计算出兔子每周营养物质的数量。简单起见,这里考虑三种对生长其重要作用的营养成分,蛋白质、矿物质和维生素。
现有五种饲料,公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。
① 决策变量:在混合饲料中,每周所需第j种饲料的斤数xj,j= 1,2,3,4,5;
③ 确定目标:混合饲料的成本最低
有5个蔬菜基地每天向3家超市供应蔬菜,其相关数据如下:
制定调运方案,既可以满足供需关系,又使运输的吨公里数达到最小。
记号说明:(xi,yi)表示蔬菜基地i 的坐标;(aj,bj)表示超市j的坐标;Cij表示基地i到超市j的距离;
si表示蔬菜基地i的产量; dj表示超市j的需求量。
如果没有等式约束,就在相应位置输入空矩阵[ ], 不等式约束和上下界也类似,最后的输入项若没有,则可省略。
由于linprog要求所有的不等式约束是“≤”的形式,所以将模型转化成为标准形式。
%因为在linprog命令中决策变量和价格向量是向量,因此应该将对应的矩阵C和X拉直变成向量形式。
%用循环生成价值变量 使用代码生成上述价值矩阵:
(1)非线性规划例子及模型的建立
例子2:电路板设计问题
就是将电路元件选择适当位置并通过导线进行连接。
确定三个模块的位置,满足下列要求的情况下使得总连线最短。
(1)满足如图的连接关系;
(2)所有元件完全位于电路板之内;
(3)三个元件为圆柱形,半径分别为0.2,0.1和0.1;
(4)元件1和元件3要求距离等于0.5。
目标函数:总距离(六条连线长度之和)最小
(2)非线性规划标准形式
非线性规划问题,可以根据是否有约束条件,可以分成无约束问题和约束优化问题;
比如前面给出的例子1就是无约束非线性规划问题,而例子2是一个约束非线性规划问题。
无约束优化问题标准形式 :
① 首先建立一个函数M文件,如fun.m
约束优化问题标准格式:
(3)非线性规划MATLAB求解命令
%约束条件的函数M文件