文章目录

1. 题目

目标函数：
min ⁡ z = 4 x 1 + x 2 \min z = 4x_1 + x_2 minz=4x1​+x2​

约束条件：
s.t. { 3 x 1 + x 2 = 3 4 x 1 + 3 x 2 ≥ 6 x 1 + 2 x 2 ≤ 4 x 1 , x 2 ≥ 0 \text{s.t.} \begin{cases} 3x_1 + x_2 = 3 \\ 4x_1 + 3x_2 \geq 6 \\ x_1 + 2x_2 \leq 4 \\ x_1, x_2 \geq 0 \end{cases} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​=34x1​+3x2​≥6x1​+2x2​≤4x1​,x2​≥0​

2. 添加松弛变量

min ⁡ z = 4 x 1 + x 2 + 0 x 3 + 0 x 4 \min z = 4x_1 + x_2 + 0x_3 + 0x_4 minz=4x1​+x2​+0x3​+0x4​

s.t. { 3 x 1 + x 2 = 3 4 x 1 + 3 x 2 − x 3 = 6 x 1 + 2 x 2 + x 4 = 4 x i ≥ 0 , i = 1 , 2 , … , 4 \text{s.t.} \begin{cases} 3x_1 + x_2 = 3 \\ 4x_1 + 3x_2 - x_3 = 6 \\ x_1 + 2x_2 + x_4 = 4 \\ x_i \geq 0, i = 1,2,\dots, 4 \end{cases} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​=34x1​+3x2​−x3​=6x1​+2x2​+x4​=4xi​≥0,i=1,2,…,4​

3. 大M法

max ⁡ − z = − 4 x 1 − x 2 + 0 x 3 + 0 x 4 − M x 5 − M x 6 \max -z = -4x_1 - x_2 + 0x_3 + 0x_4 - Mx_5 - Mx_6 max−z=−4x1​−x2​+0x3​+0x4​−Mx5​−Mx6​

s.t. { 3 x 1 + x 2 + x 5 = 3 4 x 1 + 3 x 2 − x 3 + x 6 = 6 x 1 + 2 x 2 + x 4 = 4 x i ≥ 0 , i = 1 , 2 , … , 6 \text{s.t.} \begin{cases} 3x_1 + x_2 + x_5 = 3 \\ 4x_1 + 3x_2 - x_3 + x_6 = 6 \\ x_1 + 2x_2 + x_4 = 4 \\ x_i \geq 0, i = 1,2,\dots, 6 \end{cases} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​+x5​=34x1​+3x2​−x3​+x6​=6x1​+2x2​+x4​=4xi​≥0,i=1,2,…,6​

单纯形表

. C C C.-4-100-M-M
C B C_B CB​基 b b b x 1 ↓ x_1 \downarrow x1​↓ x 2 x_2 x2​ x 3 x_3 x3​ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
-M ← x 5 \leftarrow x_5 ←x5​3[3]10010
-M x 6 x_6 x6​643-1001
0 x 4 x_4 x4​4120100
. σ \sigma σ.7M-44M-1-M000

入基变量 x 1 x_1 x1​，出基变量 x 5 x_5 x5​；

. C C C.-4-100-M-M
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 ↓ x_2 \downarrow x2​↓ x 3 x_3 x3​ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
-4 x 1 x_1 x1​11 1 3 \frac{1}{3} 31​00 1 3 \frac{1}{3} 31​0
-M ← x 6 \leftarrow x_6 ←x6​20[ 5 3 \frac{5}{3} 35​]-10- 4 3 \frac{4}{3} 34​1
0 x 4 x_4 x4​30 5 3 \frac{5}{3} 35​01- 1 3 \frac{1}{3} 31​0
. σ \sigma σ.0 5 3 \frac{5}{3} 35​M+ 1 3 \frac{1}{3} 31​-M0- 7 3 \frac{7}{3} 37​M+ 4 3 \frac{4}{3} 34​0

入基变量 x 2 x_2 x2​，出基变量 x 6 x_6 x6​；

. C C C.-4-100-M-M
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 x_2 x2​ x 3 ↓ x_3 \downarrow x3​↓ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
-4 x 1 x_1 x1​ 3 5 \frac{3}{5} 53​10 1 5 \frac{1}{5} 51​0 1 15 \frac{1}{15} 151​- 1 5 \frac{1}{5} 51​
-1 x 2 x_2 x2​ 6 5 \frac{6}{5} 56​01 − 3 5 -\frac{3}{5} −53​0 − 4 5 -\frac{4}{5} −54​ 3 5 \frac{3}{5} 53​
0 ← x 4 \leftarrow x_4 ←x4​100[1]11-1
. σ \sigma σ.00 1 5 \frac{1}{5} 51​0-M- 8 15 \frac{8}{15} 158​-M- 1 5 \frac{1}{5} 51​

入基变量 x 3 x_3 x3​，出基变量 x 4 x_4 x4​；

. C C C.-4-100-M-M
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 x_2 x2​ x 3 x_3 x3​ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
-4 x 1 x_1 x1​ 2 5 \frac{2}{5} 52​100- 1 5 \frac{1}{5} 51​- 2 15 \frac{2}{15} 152​0
-1 x 2 x_2 x2​ 9 5 \frac{9}{5} 59​010 3 5 \frac{3}{5} 53​ − 1 5 -\frac{1}{5} −51​0
0 x 3 x_3 x3​100111-1
. σ \sigma σ.000 − 1 5 -\frac{1}{5} −51​-M- 11 15 \frac{11}{15} 1511​-M

所有的 σ j ≤ 0 \sigma_j \leq 0 σj​≤0，且所有的人工变量都是非基变量。
得到最优解：
x ∗ = ( 2 5 , 9 5 , 1 , 0 ) T ， x^* = (\frac{2}{5}, \frac{9}{5}, 1, 0)^T， x∗=(52​,59​,1,0)T，

z ∗ = 4 x 1 + x 2 = 4 ∗ 2 5 + 9 5 = 17 5 . z* = 4x_1 + x_2 = 4*\frac{2}{5} + \frac{9}{5} = \frac{17}{5}. z∗=4x1​+x2​=4∗52​+59​=517​.

4. 两阶段法

  • 第一阶段：
    min ⁡ w = 0 x 1 + 0 x 2 + 0 x 3 + 0 x 4 + x 5 + x 6 \min w = 0x_1 + 0x_2 + 0x_3 + 0x_4 + x_5 + x_6 minw=0x1​+0x2​+0x3​+0x4​+x5​+x6​

⇔ \Leftrightarrow ⇔

max ⁡ − w = 0 x 1 + 0 x 2 + 0 x 3 + 0 x 4 − x 5 − x 6 \max -w = 0x_1 + 0x_2 + 0x_3 + 0x_4 - x_5 - x_6 max−w=0x1​+0x2​+0x3​+0x4​−x5​−x6​

s.t. { 3 x 1 + x 2 + x 5 = 3 4 x 1 + 3 x 2 − x 3 + x 6 = 6 x 1 + 2 x 2 + x 4 = 4 x i ≥ 0 , i = 1 , 2 , … , 6 \text{s.t.} \begin{cases} 3x_1 + x_2 + x_5 = 3 \\ 4x_1 + 3x_2 - x_3 + x_6 = 6 \\ x_1 + 2x_2 + x_4 = 4 \\ x_i \geq 0, i = 1,2,\dots, 6 \end{cases} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​+x5​=34x1​+3x2​−x3​+x6​=6x1​+2x2​+x4​=4xi​≥0,i=1,2,…,6​

单纯形表

. C C C.0000-1-1
C B C_B CB​基 b b b x 1 ↓ x_1 \downarrow x1​↓ x 2 x_2 x2​ x 3 x_3 x3​ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
-1 ← x 5 \leftarrow x_5 ←x5​3[3]10010
-1 x 6 x_6 x6​643-1001
0 x 4 x_4 x4​4120100
. σ \sigma σ.74-1000

入基变量 x 1 x_1 x1​，出基变量 x 5 x_5 x5​；

. C C C.0000-1-1
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 ↓ x_2 \downarrow x2​↓ x 3 x_3 x3​ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
0 x 1 x_1 x1​11 1 3 \frac{1}{3} 31​00 1 3 \frac{1}{3} 31​0
-1 ← x 6 \leftarrow x_6 ←x6​20[ 5 3 \frac{5}{3} 35​]-10- 4 3 \frac{4}{3} 34​1
0 x 4 x_4 x4​30 5 3 \frac{5}{3} 35​01- 1 3 \frac{1}{3} 31​0
. σ \sigma σ.0 5 3 \frac{5}{3} 35​-10- 7 3 \frac{7}{3} 37​0

入基变量 x 2 x_2 x2​，出基变量 x 6 x_6 x6​；

. C C C.0000-1-1
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 x_2 x2​ x 3 x_3 x3​ x 4 x_4 x4​ x 5 x_5 x5​ x 6 x_6 x6​
0 x 1 x_1 x1​ 3 5 \frac{3}{5} 53​10 1 5 \frac{1}{5} 51​0 1 15 \frac{1}{15} 151​- 1 5 \frac{1}{5} 51​
0 x 2 x_2 x2​ 6 5 \frac{6}{5} 56​01 − 3 5 -\frac{3}{5} −53​0 − 4 5 -\frac{4}{5} −54​ 3 5 \frac{3}{5} 53​
0 x 4 x_4 x4​100111-1
. σ \sigma σ.000000

第一阶段结束。

  • 第二阶段

max ⁡ − z = − 4 x 1 − x 2 + 0 x 3 + 0 x 4 \max -z = -4x_1 - x_2 + 0x_3 + 0x_4 max−z=−4x1​−x2​+0x3​+0x4​

. C C C.-4-100
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 x_2 x2​ x 3 ↓ x_3 \downarrow x3​↓ x 4 x_4 x4​
-4 x 1 x_1 x1​ 3 5 \frac{3}{5} 53​10 1 5 \frac{1}{5} 51​0
-1 x 2 x_2 x2​ 6 5 \frac{6}{5} 56​01 − 3 5 -\frac{3}{5} −53​0
0 ← x 4 \leftarrow x_4 ←x4​100[1]1
. σ \sigma σ.00 1 5 \frac{1}{5} 51​0

入基变量 x 3 x_3 x3​，出基变量 x 4 x_4 x4​；

. C C C.-4-100
C B C_B CB​基 b b b x 1 x_1 x1​ x 2 x_2 x2​ x 3 x_3 x3​ x 4 x_4 x4​
-4 x 1 x_1 x1​ 2 5 \frac{2}{5} 52​100- 1 5 \frac{1}{5} 51​
-1 x 2 x_2 x2​ 9 5 \frac{9}{5} 59​010 3 5 \frac{3}{5} 53​
0 x 3 x_3 x3​10011
. σ \sigma σ.000 − 1 5 -\frac{1}{5} −51​

第二阶段结束。

最优解
x ∗ = ( 2 5 , 9 5 , 1 , 0 ) T ， x^* = (\frac{2}{5}, \frac{9}{5}, 1, 0)^T， x∗=(52​,59​,1,0)T，

z ∗ = 4 x 1 + x 2 = 4 ∗ 2 5 + 9 5 = 17 5 . z^* = 4x_1 + x_2 = 4*\frac{2}{5} + \frac{9}{5} = \frac{17}{5}. z∗=4x1​+x2​=4∗52​+59​=517​.

图片来自网络

Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

avatar GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

avatar GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m

avatar GitCode 开源社区