加拿大约克大学线性规划课程初级指南

在数学中，线性规划是一种在一定约束条件下优化运算的方法。线性规划的主要目标是最大化或最小化数值。它由受线性方程或不等式形式约束的线性函数组成。线性规划被认为是一种重要的技术，用于寻找资源的最佳利用方式。线性规划 "一词由两个词组成：线性和规划。线性 "一词定义了多个变量之间的一级关系。而 "编程 "一词则定义了从多个备选方案中选择最佳解决方案的过程。本文将介绍线性规划的定义、其组成部分以及解决线性规划问题的不同方法。

1.什么是线性规划?

线性规划(LP)或线性优化可定义为在线性约束条件下最大化或最小化线性函数的问题。约束条件可以是等式或不等式。优化问题涉及损益计算。 线性规划问题是一类重要的优化问题，有助于找到可行区域并优化解决方案，以实现函数的最高值或最低值。

换句话说，线性规划是一种优化方法，可使数学模型的目标函数最大化或最小化，而数学模型的一系列要求则由线性关系表示。线性规划的主要目标是找到最优解。

线性规划是一种评估与特定情况相关的各种不等式并计算在这些条件下可获得的最佳值的方法。使用线性规划时的一些假设如下：

a.必须量化约束条件的数量。

b.约束条件与目标函数之间必须是线性关系。

c.必须优化线性函数(即目标函数)。

2.线性规划的组成部分

线性规划的基本组成部分如下：决策变量、决策条件、数据、目标函数。

3.线性规划的特点

以下是线性规划的五个特点：

a.约束条件 - 约束条件必须用资源的数学形式表示。

b.目标函数 - 在问题中，目标函数应以定量方式定义。

c.线性 - 函数中两个或多个变量之间的关系应是线性的。也就是说，变量的度数为一。

d.有限性 - 输入和输出数必须有有限和无限之分。如果函数有无限因子，则最优解不可行。

e.非负值 - 变量的值必须为正或零。不应该是负值。

d.决策变量 - 决策变量决定结果。它提供了问题的最终解决方案。对于任何问题，第一步都是确定决策变量。

4.线性规划问题

线性规划(LP)问题是与寻找线性函数的最优值有关的问题。最优值可以是最大值，也可以是最小值。给定的线性函数被视为目标函数。目标函数可以包含多个带有约束条件的变量，并且必须满足一组称为线性约束条件的线性不等式。线性规划问题可用于寻找生产、供应、运输和分配等方面的最佳解决方案。

5.解决线性规划问题的方法

线性规划问题可以用多种方法来解决，如图形法、单纯形法或使用 R、open solver 等工具。下面，我们将详细介绍两种最重要的方法，即单纯形法和图形法。

6.线性规划的单纯形法

单纯形法是解决线性规划问题最常用的方法之一。它是一个寻找最优解的迭代过程。在这种方法中，基础变量的值不断变化，以获得目标函数的最大值。下面介绍线性规划的单纯形法算法：

步骤1：创建问题(写出不等式的约束条件和目标函数)。

步骤2： 在每个不等式表达式中加入弱变量，将给定的不等式转换为方程。

步骤3：创建原始的单纯形表格。将目标函数写在最下面一行。每个不等式约束都出现在各自的一行。现在，我们可以用一个称为原始单纯形表的展开矩阵来表示问题。

步骤4;确定最下面一行中最大的负条目，这有助于确定坐标轴上的列。最下面一行的最大负条目决定了目标函数的最大系数，这将帮助我们尽快实现目标函数值的最大化。

步骤5： 计算系数 要计算系数，我们需要用最右边一列的条目除以第一列(不包括最下面一行)的条目。系数最小的一行就是该行。这一步中确定的行和这一步中确定的元素将作为枢轴元素。

步骤6：进行旋转，使该列中的所有其他元素都等于零。

步骤7：如果最下面一行中没有负元素，则过程结束。如果没有，则从第 4 步重新开始。

步骤8：最后确定与最终单纯形表格相关的解。

海马课堂专业课程辅导，2300+严选硕博学霸师资，针对学生的薄弱科目和学校教学进度，匹配背景相符的导师，根据学生情况进行1V1专属备课，上课时间灵活安排，中英双语详细讲解课程中的考点、难点问题，并提供多方位的课后辅导，辅助学生掌握全部课程知识，补足短板。