会计学线性规划(xiànxìnɡɡuīhuá)：目标函数是线性的，约束条件是线性等式或不等式线性规划(xiànxìnɡɡuīhuá)的历史///◎问题：确定食品数量，满足(mǎnzú)营养需求，花费最小？例2.运输(yùnshū)问题例3.其它(qítā)应用线性规划(xiànxìnɡɡuīhuá)的一般形式线性规划的标准形(分析(fēnxī)、算法)一般(yībān)形式标准形例5.化成(huàchénɡ)标准形定义(dìngyì)：给定含有n个变量，m个方程的线性方程组Ax=b，设B是由A的列组成的任一非奇异m×m子阵，则如果置x的所有与B无关的n-m个分量为零后，所得方程组的解是Ax=b关于基B的基本解(basicsolution)，称x中与基B对应的分量为基变量(basicvariables)退化基本解：基本解中如果有一个或多个基变量的值为零基本(jīběn)可行解线性规划的基本(jīběn)定理与凸性的关系(guānxì)凸性(凸集及性质(xìngzhì))一些(yīxiē)重要的凸集极点(jídiǎn)极点(jídiǎn)与基本可行解的等价性定理例2.例3.线性规划解的几何(jǐhé)特征线性规划解的几何(jǐhé)特征顶点线性规划问题解的几种(jǐzhǒnɡ)情况单纯形法简介(jiǎnjiè)1.转轴(基本(jīběn)解→相邻基本(jīběn)解)规范(guīfàn)形(canonicalform)规范(guīfàn)形的转换问题转轴(zhuànzhóu)(pivot)转轴转轴2.BFS→相邻(xiānɡlín)BFS(极点→相邻(xiānɡlín)极点)确定(quèdìng)离基变量例3.考虑(kǎolǜ)线性方程组3.BFS→目标值减小的相邻(xiānɡlín)BFS相对(xiāngduì)/既约费用系数(relative/reducedcostcoefficients)确定(quèdìng)进基变量4.计算(jìsuàn)过程－单纯形法单纯形法的步骤(bùzhòu)例1.转轴最优解：退化(tuìhuà)(degenerate)与循环(cycling)最小系数(xìshù)规则：//循环(xúnhuán)！避免(bìmiǎn)循环的方法前四张单纯形表相同(xiānɡtónɡ)！最后(zuìhòu)一张单纯形表/最优单纯形表单纯形法的收敛性5.两阶段法如何启动(qǐdòng)单纯形法－人工变量得到原问题(wèntí)的基本可行解例1.第一张单纯形表辅助(fǔzhù)问题的最优值是0.两阶段(jiēduàn)法－可求任一线性规划问题例2.原问题的最优解：6.修正(xiūzhèng)单纯形法(Revisedsimplexmethod)7.单纯形法的矩阵(jǔzhèn)形式初始(chūshǐ)表格－单纯形表修正单纯形法的计算(jìsuàn)步骤基的转换(zhuǎnhuàn)定理相关数据(shùjù)的更新－初等行变换例1a2进基，计算y2.计算表格(biǎogé)如下：a1进基，计算y1.得如下(rúxià)表格：最优值：利用两阶段(jiēduàn)单纯形过程求解///