{"id":44436,"date":"2024-05-19T06:29:28","date_gmt":"2024-05-19T06:29:28","guid":{"rendered":"https:\/\/science-hub.click\/%E7%B7%9A%E5%BD%A2%E8%A8%88%E7%94%BB%E6%B3%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC\/"},"modified":"2024-05-19T06:29:28","modified_gmt":"2024-05-19T06:29:28","slug":"%E7%B7%9A%E5%BD%A2%E8%A8%88%E7%94%BB%E6%B3%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC","status":"publish","type":"post","link":"https:\/\/science-hub.click\/?p=44436","title":{"rendered":"\u7dda\u5f62\u8a08\u753b\u6cd5\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac"},"content":{"rendered":"

\u5c0e\u5165<\/h2>

\u6570\u5b66\u306b\u304a\u3051\u308b\u7dda\u5f62\u8a08\u753b\u6cd5<\/b>(LP) \u554f\u984c\u306f\u3001\u76ee\u7684\u95a2\u6570\u3068\u5236\u7d04\u304c\u3059\u3079\u3066\u7dda\u5f62\u3067\u3042\u308b\u6700\u9069\u5316\u554f\u984c\u3067\u3059\u3002\u305f\u3060\u3057\u3001\u3053\u3053\u3067\u793a\u3057\u305f\u7d50\u679c\u306e\u307b\u3068\u3093\u3069\u306f\u3001\u76ee\u7684\u304c\u8003\u616e\u3055\u308c\u3066\u3044\u308b\u5404\u5909\u6570<\/a><\/span>\u306e\u5358\u8abf\u5897\u52a0\u95a2\u6570\u3067\u3042\u308b\u5834\u5408\u306b\u3082\u5f53\u3066\u306f\u307e\u308a\u307e\u3059\u3002\u7dda\u5f62\u8a08\u753b\u6cd5\u306f\u3001<\/a><\/span>\u7dda\u5f62\u554f\u984c\u3092\u89e3\u6c7a\u3059\u308b\u65b9\u6cd5\u3082\u6307\u3057\u307e\u3059\u3002<\/p>

LP \u554f\u984c\u306f\u6700\u3082\u7c21\u5358\u306a\u6700\u9069\u5316\u554f\u984c\u3067\u3042\u308a\u3001\u3059\u3079\u3066\u306e\u5236\u7d04\u304c\u7dda\u5f62\u3067\u3042\u308b\u305f\u3081\u3001\u7dda\u5f62\u8a08\u753b\u6cd5\u306f<\/a><\/span>\u6700\u9069\u5316\u306e\u4e2d\u5fc3\u9818\u57df\u3067\u3059\u3002\u5b9f\u969b\u306e \u30aa\u30da\u30ec\u30fc\u30b7\u30e7\u30f3\u30ba \u30ea\u30b5\u30fc\u30c1\u306e<\/span>\u554f\u984c\u306e\u591a\u304f\u306f\u3001PL \u554f\u984c\u3068\u3057\u3066\u8868\u73fe\u3067\u304d\u307e\u3059\u3002\u3053\u306e\u305f\u3081\u3001\u4ed6\u306e\u6700\u9069\u5316\u554f\u984c\u3092\u89e3\u6c7a\u3059\u308b\u305f\u3081\u306e\u591a\u6570<\/a><\/span>\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u7dda\u5f62\u554f\u984c\u306e\u89e3\u6c7a\u306b\u57fa\u3065\u3044\u3066\u3044\u307e\u3059\u3002<\/p>

\u7dda\u5f62\u8a08\u753b\u6cd5\u3068\u3044\u3046\u7528\u8a9e\u306f\u3001\u6c42\u3081\u3089\u308c\u308b\u89e3\u304c\u5b9f\u6570\u5909\u6570\u3067\u8868\u73fe\u3055\u308c\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u3053\u3068\u3092\u524d\u63d0\u3068\u3057\u3066\u3044\u307e\u3059\u3002\u554f\u984c\u306e\u30e2\u30c7\u30ea\u30f3\u30b0 (\u3044\u308f\u3086\u308b\u6574\u5408\u6027<\/i>\u5236\u7d04) \u3067\u96e2\u6563\u5909\u6570\u3092\u4f7f\u7528\u3059\u308b\u5fc5\u8981\u304c\u3042\u308b\u5834\u5408\u306f\u3001\u6574\u6570\u306e\u7dda\u5f62\u8a08\u753b\u6cd5 (PLNE) \u306b\u3064\u3044\u3066\u8a71\u3057\u307e\u3059\u3002\u5f8c\u8005\u306f\u9023\u7d9a\u5909\u6570\u3092\u4f7f\u7528\u3057\u305f PL \u3088\u308a\u3082\u89e3\u304f\u306e\u304c\u5927\u5e45\u306b\u8907\u96d1\u3067\u3042\u308b\u3053\u3068\u3092\u77e5\u3063\u3066\u304a\u304f\u3053\u3068\u304c\u91cd\u8981\u3067\u3059\u3002<\/p>

\n\"\u7dda\u5f62\u8a08\u753b\u6cd5\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\"<\/figure>

\u4f8b<\/h2>

H<\/i>\u30d8\u30af\u30bf\u30fc\u30eb\u306b\u7b49\u3057\u3044\u9762\u7a4d\u306e<\/a><\/span>\u571f\u5730\u3092\u6240\u6709\u3057\u3001\u5c0f\u9ea6<\/a><\/span>\u3084\u30c8\u30a6\u30e2\u30ed\u30b3\u30b7\u3092<\/a><\/span>\u690d\u3048\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u8fb2\u5bb6<\/a><\/span>\u3092\u8003\u3048\u3066\u307f\u307e\u3057\u3087\u3046\u3002\u8fb2\u5bb6\u306f\u91cf<\/a><\/span>E<\/i>\u306e\u80a5\u6599<\/a><\/span>\u3068I<\/i>\u306e\u6bba\u866b\u5264<\/a><\/span>\u3092\u6301\u3063\u3066\u3044\u307e\u3059\u3002\u5c0f\u9ea6\u306b\u306f\u30011 \u30d8\u30af\u30bf\u30fc\u30eb\u3042\u305f\u308aE<\/i> 1<\/sub>\u306e\u91cf\u306e\u80a5\u6599\u3068\u30011 \u30d8\u30af\u30bf\u30fc\u30eb\u3042\u305f\u308aI<\/i> 1<\/sub>\u306e\u6bba\u866b\u5264\u304c\u5fc5\u8981\u3067\u3059\u3002\u30c8\u30a6\u30e2\u30ed\u30b3\u30b7\u306e\u5bfe\u5fdc\u3059\u308b\u91cf\u306fE<\/i> 2<\/sub>\u304a\u3088\u3073I<\/i> 2<\/sub>\u3067\u793a\u3055\u308c\u307e\u3059\u3002<\/p>

P<\/i> 1 \u3092<\/sub>\u5c0f\u9ea6\u306e\u8ca9\u58f2\u4fa1\u683c\u3001 P<\/i> 2 \u3092<\/sub>\u30c8\u30a6\u30e2\u30ed\u30b3\u30b7\u306e\u8ca9\u58f2\u4fa1\u683c\u3068\u3057\u307e\u3059\u3002\u5c0f\u9ea6\u3068\u30c8\u30a6\u30e2\u30ed\u30b3\u30b7\u3092\u690d\u3048\u308b\u30d8\u30af\u30bf\u30fc\u30eb\u306e\u6570\u3092x<\/i> 1<\/sub>\u3068x<\/i> 2<\/sub>\u3067\u8868\u3059\u3068\u3001\u5c0f\u9ea6\u3068\u30c8\u30a6\u30e2\u30ed\u30b3\u30b7\u3092\u690d\u3048\u308b\u6700\u9069\u306a\u30d8\u30af\u30bf\u30fc\u30eb\u6570\u306f\u7dda\u5f62\u30d7\u30ed\u30b0\u30e9\u30e0\u3068\u3057\u3066\u8868\u3059\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002<\/p>
\u6700\u5927\u5316\u3059\u308b<\/span><\/td>D1<\/i> \u00d7<\/i> 1<\/sub> +<\/sub> D2<\/i> \u00d7<\/i> 2<\/sub>\u200b<\/sub><\/span><\/td> \uff08\u7d14\u5229\u76ca\u306e\u6700\u5927\u5316\uff09<\/td><\/tr>
\u5236\u7d04\u306e\u4e0b\u3067<\/span><\/td>
$$ { x_1 + x_2 \\le H } $$<\/div><\/td>
 \uff08\u7dcf<\/a><\/span>\u30d8\u30af\u30bf\u30fc\u30eb\u6570\u306e\u5236\u9650\uff09 <\/td><\/tr>
$$ { E_1 x_1 + E_2 x_2 \\le E } $$<\/div><\/td>
 \uff08\u80a5\u6599\u306e\u91cf\u306e\u5236\u9650\uff09 <\/td><\/tr>
$$ { I_1 x_1 + I_2 x_2 \\le I } $$<\/div><\/td>
 \uff08\u6bba\u866b\u5264\u306e\u4f7f\u7528\u91cf\u5236\u9650\uff09 <\/td><\/tr>
$$ { x_1 \\ge 0,\\, x_2 \\ge 0 } $$<\/div><\/td>
 (\u8ca0\u306e\u30d8\u30af\u30bf\u30fc\u30eb\u6570\u3092<\/a><\/span>\u690d\u3048\u308b\u3053\u3068\u306f\u3067\u304d\u307e\u305b\u3093)<\/td><\/tr><\/table>
\n\"\u7dda\u5f62\u8a08\u753b\u6cd5\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\"<\/figure>

\u4e8c\u5143\u6027<\/h2>

\u3059\u3079\u3066\u306e\u7dda\u5f62\u30d7\u30ed\u30b0\u30e9\u30e0\u306f\u6b21\u306e\u5f62\u5f0f\u3067\u8a18\u8ff0\u3067\u304d\u307e\u3059\u3002<\/p>

\u3053\u3053\u3067\u3001 c<\/i><\/span>\u3068x \u306f<\/i><\/span>\u30b5\u30a4\u30ban<\/i><\/span>\u306e\u30d9\u30af\u30c8\u30eb\u3001 b \u306f<\/i><\/span>\u30b5\u30a4\u30bam<\/i><\/span>\u306e\u30d9\u30af\u30c8\u30eb<\/a><\/span>\u3001 A \u306f<\/i><\/span>\u30b5\u30a4\u30ba\u306e\u884c\u5217\u3067\u3059

$$ {m \\times n} $$<\/div> \u3002\u3053\u306e\u8868\u73fe\u3092\u300c\u4e3b\u5f62\u5f0f\u300d<\/i>\u3068\u3044\u3046\u7528\u8a9e\u3067\u8868\u3059\u3068\u3001\u6b21\u306e\u554f\u984c\u3092\u300c\u53cc\u5bfe\u5f62\u5f0f\u300d\u3068\u3044\u3046<\/i>\u7528\u8a9e\u3067\u8868\u3059\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002<\/p>

\u3053\u3053\u3067\u3001 A<\/i><\/span> \u3001 b<\/i><\/span> \u3001 c<\/i><\/span>\u306f\u540c\u3058\u3067\u3042\u308a\u3001 y \u306f\u30b5\u30a4\u30bam<\/i><\/span>\u306e\u30d9\u30af\u30c8\u30eb\u3067\u3059<\/i><\/span>\u3002<\/p>

2 \u3064\u306e\u554f\u984c\u306f\u975e\u5e38\u306b\u5f37\u304f\u95a2\u9023\u3057\u3066\u3044\u307e\u3059\u3002\u305d\u306e\u3046\u3061\u306e 1 \u3064\u304c\u6700\u9069\u306a\u89e3\u6c7a\u7b56\u3092\u6301\u3063\u3066\u3044\u308b\u5834\u5408\u3001\u3082\u3046\u4e00\u65b9\u3082\u6700\u9069\u306a\u89e3\u6c7a\u7b56\u3092\u6301\u3063\u3066\u3044\u307e\u3059\u3002\u3055\u3089\u306b\u3001\u4e21\u65b9\u306e\u89e3\u306f\u540c\u3058\u5024\u306b\u306a\u308a\u307e\u3059 ( w<\/i> *<\/sup> = z<\/i> *<\/sup><\/span> )\u3002\u305d\u306e\u3046\u3061\u306e 1 \u3064\u304c\u5236\u9650\u3055\u308c\u3066\u3044\u306a\u3044\u5834\u5408\u3001\u3082\u3046 1 \u3064\u306f\u89e3\u6c7a\u7b56\u304c\u3042\u308a\u307e\u305b\u3093\u3002<\/p>

\u53cc\u5bfe\u554f\u984c\u306b\u306f\u3001\u7406\u8ad6\u7684\u306a\u9762\u767d\u3055\u306b\u52a0\u3048\u3066\u3001\u975e\u5e38\u306b\u8208\u5473\u6df1\u3044\u7d4c\u6e08\u7684\u5fdc\u7528\u3082\u3042\u308a\u307e\u3059\u3002\u5404\u4e3b\u5236\u7d04\u306f\u4e8c\u91cd\u5909\u6570\u306b\u5bfe\u5fdc\u3057\u307e\u3059\u3002\u6700\u9069\u89e3\u306b\u304a\u3051\u308b\u3053\u306e\u5909\u6570\u306e\u5024\u306f\u3001\u4e3b\u5236\u7d04\u306b\u95a2\u9023\u4ed8\u3051\u3089\u308c\u305f\u9650\u754c<\/a><\/span>\u8cbb\u7528\u3092\u8868\u3057\u307e\u3059\u3002<\/p>

\n\"\u7dda\u5f62\u8a08\u753b\u6cd5\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\"<\/figure>

\u7406\u8ad6<\/h2>

\u524d\u306e\u4f8b\u304c\u793a\u3059\u3088\u3046\u306b\u3001\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u306f\u3001\u305f\u3068\u3048\u3070n \u500b\u306e<\/i>\u5909\u6570\u3092\u6c7a\u5b9a\u3059\u308b\u3053\u3068\u3067\u69cb\u6210\u3055\u308c\u307e\u3059\u3002

$$ {x_1, \\cdots, x_n} $$<\/div>\u76f4\u7dda\u7684\u306a\u76ee\u6a19\u3092\u6700\u5927\u5316\u3059\u308b<\/b>\u305f\u3081\u306b<\/p>
$$ {L(x_1, \\cdots, x_n) = \\sum_{i=1}^n c_i x_i} $$<\/div><\/dd><\/dl><\/dd><\/dl>

\u305f\u3068\u3048\u3070\u6b21\u306em<\/i>\u4e0d\u7b49\u5f0f\u306a\u3069\u3001\u3055\u307e\u3056\u307e\u306a\u5236\u7d04\u306e\u4e0b\u3067<\/p>

$$ {\\sum_{j=1}^n A_{i,j} x_j \\leq b_i} $$<\/div><\/dd><\/dl><\/dd><\/dl>

\u79c1\u306f<\/i>1 \u304b\u3089m<\/i>\u307e\u3067\u306e\u7bc4\u56f2\u3067\u3059\u3002\u3053\u306e\u3088\u3046\u306a\u5236\u7d04\u306b\u3088\u308a\u3001\u6b21\u306e\u3088\u3046\u306a\u7b26\u53f7\u5236\u7d04\u3092\u542b\u3081\u308b\u3053\u3068\u304c\u53ef\u80fd\u306b\u306a\u308a\u307e\u3059\u3002

$$ {x_1 \\geq 0} $$<\/div>\u307e\u305f\u306f
$$ {x_1 \\leq 0} $$<\/div> \u3002\u6a19\u6e96\u5f62\u5f0f<\/b>\u306e\u884c\u5217\u8a18\u8ff0\u3092\u63a1\u7528\u3059\u308b\u3068\u3001 <\/p>
$$ { \\begin{array}{rrll} \\max L(x) = & {}^tc\\,x & &\\\\ s.c & Ax &\\leq& b\\\\ & x &\\geq&0 \\end{array} } $$<\/div><\/dd><\/dl>

\u7dda\u5f62\u8a08\u753b\u6cd5\u3067\u306f\u3001\u76ee\u7684\u95a2\u6570\u3092\u6700\u5c0f\u5316\u3059\u308b\u3053\u3068\u3092\u8a66\u307f\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002\u6700\u5927\u5316\u3092\u56f3\u308b\u3053\u3068\u3067\u3001\u524d\u306e\u30b1\u30fc\u30b9 (\u6a19\u6e96\u5f62\u5f0f) \u306b\u623b\u308a\u307e\u3059\u3002

$$ {-L(x_1,\\cdots,x_n)} $$<\/div> \u3002<\/p>

\u5e7e\u4f55\u5b66\u7684\u89b3\u70b9<\/a><\/span>\u304b\u3089\u898b\u308b<\/a><\/span>\u3068\u3001\u7dda\u5f62\u62d8\u675f\u306f\u51f8<\/span>\u591a\u9762\u4f53<\/a><\/span>(\u307e\u305f\u306f\u591a\u9762\u4f53) \u3092\u5f62\u6210\u3057\u307e\u3059\u3002\u76ee\u7684\u95a2\u6570\u3082\u7dda\u5f62\u306e\u5834\u5408\u3001\u3059\u3079\u3066\u306e\u5c40\u6240\u6700\u9069\u5024\u306f\u5927\u57df\u6700\u9069\u5024\u3067\u3082\u3042\u308a\u307e\u3059\u3002\u3053\u308c\u306f\u3001\u8003\u616e\u3055\u308c\u308b\u5404\u5909\u6570\u3067\u5358\u8abf\u5897\u52a0\u3059\u308b\u5834\u5408\u306b\u5f53\u3066\u306f\u307e\u308a\u307e\u3059\u3002\u7dda\u5f62\u30b1\u30fc\u30b9\u306f\u3001\u30d7\u30ed\u30d1\u30c6\u30a3\u304c\u4f7f\u7528\u3055\u308c\u306a\u3044\u7279\u5b9a\u306e\u30b1\u30fc\u30b9\u306e\u307f\u3092\u8868\u3057\u307e\u3059\u3002<\/p>

\u6700\u9069\u306a\u89e3\u6c7a\u7b56\u304c\u5b58\u5728\u3057\u306a\u3044\u30b1\u30fc\u30b9\u304c 2 \u3064\u3042\u308a\u307e\u3059\u3002 1 \u3064\u76ee\u306f\u3001\u5236\u7d04\u304c\u4e92\u3044\u306b\u77db\u76fe\u3059\u308b\u5834\u5408\u3067\u3059 (\u4f8b:

$$ {((x \\ge 2) \\wedge (x \\le 1))} $$<\/div> \uff09\u3002\u3053\u306e\u3088\u3046\u306a\u5834\u5408\u3001\u30dd\u30ea\u30c8\u30fc\u30d7\u306f\u7a7a\u3067\u3042\u308a\u3001\u89e3\u304c\u307e\u3063\u305f\u304f<\/a><\/span>\u5b58\u5728\u3057\u306a\u3044\u305f\u3081\u3001\u6700\u9069\u89e3\u306f\u5b58\u5728\u3057\u307e\u305b\u3093\u3002\u305d\u306e\u5834\u5408\u3001PL \u306f\u5b9f\u884c\u4e0d\u53ef\u80fd\u306b<\/i>\u306a\u308a\u307e\u3059\u3002<\/p>

\u591a\u9762\u4f53\u306f\u3001\u76ee\u7684\u95a2\u6570\u3067\u5b9a\u7fa9\u3055\u308c\u305f\u65b9\u5411\u306b\u7121\u5236\u9650\u306b\u3059\u308b\u3053\u3068\u3082\u3067\u304d\u307e\u3059 (\u305f\u3068\u3048\u3070\u3001\u6b21\u306e\u3088\u3046\u306ax<\/i> 1<\/sub> + 3 x<\/i> 2)<\/sub><\/span> \u3002

$$ {x_1 \\ge 0} $$<\/div> \u3001
$$ {x_2 \\ge 0} $$<\/div> \u3001
$$ {x_1 + x_2 \\ge 10} $$<\/div> \uff09\u3002\u3053\u306e\u5834\u5408\u3001\u76ee\u7684\u95a2\u6570\u306e\u4efb\u610f\u306e\u9ad8\u3044\uff08\u307e\u305f\u306f\u4f4e\u3044\uff09\u5024\u3067\u5236\u7d04\u3092\u6e80\u305f\u3059\u89e3\u3092\u69cb\u7bc9\u3059\u308b\u3053\u3068\u304c\u53ef\u80fd\u3067\u3042\u308b\u305f\u3081\u3001\u6700\u9069\u306a\u89e3\u306f\u5b58\u5728\u3057\u307e\u305b\u3093\u3002<\/p>

\u3053\u308c\u3089 2 \u3064\u306e\u30b1\u30fc\u30b9 (\u5b9f\u969b\u306e\u554f\u984c\u3067\u306f\u7a76\u6975\u7684\u306b\u306f\u307e\u308c\u3067\u3059) \u3092\u9664\u3051\u3070\u3001\u6700\u9069\u5024\u306f\u5e38\u306b\u591a\u9762\u4f53\u306e\u9802\u70b9\u3067\u9054\u6210\u3055\u308c\u307e\u3059\u3002\u305f\u3060\u3057\u3001\u6700\u9069\u89e3\u306f\u5fc5\u305a\u3057\u3082\u4e00\u610f\u3067\u3042\u308b\u3068\u306f\u9650\u308a\u307e\u305b\u3093\u3002\u30dd\u30ea\u30c8\u30fc\u30d7\u306e\u30a8\u30c3\u30b8\u3084\u9762\u3001\u3042\u308b\u3044\u306f\u30dd\u30ea\u30c8\u30fc\u30d7\u5168\u4f53\u306b\u5bfe\u5fdc\u3059\u308b\u6700\u9069\u89e3\u306e\u30bb\u30c3\u30c8<\/a><\/span>\u3092\u6301\u3064\u3053\u3068\u3082\u53ef\u80fd\u3067\u3059\u3002<\/p><\/div>

\n\"\u7dda\u5f62\u8a08\u753b\u6cd5\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\"<\/figure>

\u53c2\u8003\u8cc7\u6599<\/h2>
  1. Line\u00eare programmering \u2013 afrikaans<\/a><\/li>
  2. \u0628\u0631\u0645\u062c\u0629 \u062e\u0637\u064a\u0629 \u2013 arabe<\/a><\/li>
  3. Programaci\u00f3n llinial \u2013 asturien<\/a><\/li>
  4. X\u0259tti proqramla\u015fd\u0131rma \u2013 azerba\u00efdjanais<\/a><\/li>
  5. \u041b\u0456\u043d\u0435\u0439\u043d\u0430\u0435 \u043f\u0440\u0430\u0433\u0440\u0430\u043c\u0430\u0432\u0430\u043d\u043d\u0435 \u2013 bi\u00e9lorusse<\/a><\/li>
  6. \u09b0\u09c8\u0996\u09bf\u0995 \u0995\u09be\u09ae\u09cd\u09af\u09a4\u09ae\u0995\u09b0\u09a3 \u2013 bengali<\/a><\/li><\/ol><\/div>\n
    \n

    \n \u7dda\u5f62\u8a08\u753b\u6cd5\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\u30fb\u95a2\u9023\u52d5\u753b\n <\/h2>\n
    \n \n
    \n
    \n