close

Вход

Забыли?

вход по аккаунту

?

Решение одной задачи линейного программирования над множествами.

код для вставкиСкачать
ȼɟɫɬɧɢɤ ɆȽɌɍ, ɬɨɦ 7, ʋ3, 2004 ɝ.
ɫɬɪ.425-428
Ɋɟɲɟɧɢɟ ɨɞɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
ɧɚɞ ɦɧɨɠɟɫɬɜɚɦɢ
ȼ.Ƚ. Ʉɭɦɚɪɨɜ
Ɇɭɪɦɚɧɫɤɢɣ ɝɨɫɭɞɚɪɫɬɜɟɧɧɵɣ ɩɟɞɚɝɨɝɢɱɟɫɤɢɣ ɭɧɢɜɟɪɫɢɬɟɬ,
ɤɚɮɟɞɪɚ ɚɥɝɟɛɪɵ, ɝɟɨɦɟɬɪɢɢ ɢ ɩɪɢɤɥɚɞɧɨɣ ɦɚɬɟɦɚɬɢɤɢ
Ⱥɧɧɨɬɚɰɢɹ. ȼ ɫɨɜɪɟɦɟɧɧɨɣ ɦɚɬɟɦɚɬɢɤɟ ɯɨɪɨɲɨ ɢɡɭɱɟɧɵ ɦɟɬɨɞɵ ɪɟɲɟɧɢɹ ɡɚɞɚɱ ɥɢɧɟɣɧɨɝɨ
ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɧɚɞ ɩɪɨɢɡɜɨɥɶɧɵɦɢ ɱɢɫɥɨɜɵɦɢ ɩɨɥɹɦɢ. ȼ ɪɚɛɨɬɟ ɨɩɢɫɚɧ ɦɟɬɨɞ ɪɟɲɟɧɢɹ ɩɪɨɫɬɟɣɲɟɣ
ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɧɚɞ ɦɧɨɠɟɫɬɜɚɦɢ ɢ ɩɪɢɜɟɞɟɧ ɩɪɢɦɟɪ ɟɟ ɷɤɨɧɨɦɢɱɟɫɤɨɝɨ ɩɪɢɥɨɠɟɧɢɹ.
Abstract. Methods of solving linear programming problems of numeric fields are well studied in the modern
mathematics. This paper includes a method of solving of the elementary transport problem in Boolean and gives
an example of its economic application.
1. ȼɜɟɞɟɧɢɟ
ȼ ɫɨɜɪɟɦɟɧɧɨɣ ɦɚɬɟɦɚɬɢɤɟ ɯɨɪɨɲɨ ɢɡɭɱɟɧɵ ɦɟɬɨɞɵ ɪɟɲɟɧɢɹ ɡɚɞɚɱ ɥɢɧɟɣɧɨɝɨ
ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɧɚɞ ɩɪɨɢɡɜɨɥɶɧɵɦɢ ɱɢɫɥɨɜɵɦɢ ɩɨɥɹɦɢ. ɉɪɢ ɪɟɲɟɧɢɢ ɠɟ ɩɪɚɤɬɢɱɟɫɤɢɯ ɡɚɞɚɱ ɱɚɫɬɨ
ɩɪɢɯɨɞɢɬɫɹ ɨɩɟɪɢɪɨɜɚɬɶ ɫ ɬɚɤɢɦɢ ɦɚɬɟɦɚɬɢɱɟɫɤɢɦɢ ɨɛɴɟɤɬɚɦɢ, ɤɚɤ ɦɧɨɠɟɫɬɜɚ. ȼ ɫɬɚɬɶɟ (Lieby Paulette,
2000) ɩɪɢɜɨɞɢɬɫɹ ɦɟɬɨɞ ɪɟɲɟɧɢɹ ɨɞɧɨɣ ɷɤɫɬɪɟɦɚɥɶɧɨɣ ɡɚɞɚɱɢ ɧɚɞ ɤɨɧɟɱɧɵɦɢ ɦɧɨɠɟɫɬɜɚɦɢ ɫ ɩɨɦɨɳɶɸ
ɚɩɩɚɪɚɬɚ ɚɧɬɢɰɟɩɟɣ.
ɐɟɥɶ ɞɚɧɧɨɣ ɪɚɛɨɬɵ – ɫɮɨɪɦɭɥɢɪɨɜɚɬɶ ɚɧɚɥɨɝ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ
ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɧɚɞ ɦɧɨɠɟɫɬɜɚɦɢ ɢ ɩɪɢɜɟɫɬɢ ɦɟɬɨɞ ɪɟɲɟɧɢɹ ɷɬɨɣ ɡɚɞɚɱɢ. ɉɪɢɦɟɪɨɦ ɷɤɨɧɨɦɢɱɟɫɤɨɝɨ
ɩɪɢɦɟɧɟɧɢɹ ɬɚɤɢɯ ɡɚɞɚɱ ɦɨɠɟɬ ɹɜɥɹɬɶɫɹ ɫɥɟɞɭɸɳɢɣ.
ɉɪɟɞɩɨɥɨɠɢɦ, ɢɦɟɟɬɫɹ m ɜɭɡɨɜ A1, …, Am ɫ ɨɩɪɟɞɟɥɟɧɧɵɦɢ ɦɧɨɠɟɫɬɜɚɦɢ a1, …, am ɜɢɞɨɜ
ɫɩɟɰɢɚɥɢɫɬɨɜ, ɤɨɬɨɪɵɟ ɞɨɥɠɧɵ ɩɪɨɣɬɢ ɫɬɚɠɢɪɨɜɤɭ ɜ ɨɞɧɨɦ ɢɡ n ɜɭɡɨɜ B1, …, Bn. ȼɭɡɵ B1, …, Bn ɞɨɥɠɧɵ
ɨɛɟɫɩɟɱɢɬɶ ɫɬɚɠɢɪɨɜɤɭ ɨɩɪɟɞɟɥɟɧɧɨɝɨ ɦɧɨɠɟɫɬɜɚ b1, …, bn ɜɢɞɨɜ ɫɩɟɰɢɚɥɢɫɬɨɜ. ɇɚ ɤɚɠɞɨɝɨ ɢɡ
ɫɩɟɰɢɚɥɢɫɬɨɜ, ɫɥɟɞɭɸɳɢɯ ɢɡ ɜɭɡɚ Ai ɜ ɜɭɡ Bj ɢ ɜɯɨɞɹɳɢɯ ɜ ɩɟɪɟɱɟɧɶ cij, ɦɢɧɢɫɬɟɪɫɬɜɨɦ ɨɛɪɚɡɨɜɚɧɢɹ
ɜɵɞɟɥɹɟɬɫɹ ɨɩɪɟɞɟɥɟɧɧɚɹ ɫɭɦɦɚ, ɪɚɜɧɚɹ 1 ɭ.ɟ. ɇɟɨɛɯɨɞɢɦɨ ɬɚɤɢɦ ɨɛɪɚɡɨɦ ɪɚɫɩɪɟɞɟɥɢɬɶ ɫɩɟɰɢɚɥɢɫɬɨɜ ɩɨ
ɜɭɡɚɦ, ɱɬɨɛɵ ɨɛɳɚɹ ɫɭɦɦɚ, ɜɵɞɟɥɹɟɦɚɹ ɦɢɧɢɫɬɟɪɫɬɜɨɦ, ɛɵɥɚ ɧɚɢɦɟɧɶɲɟɣ.
2. ɉɨɫɬɚɧɨɜɤɚ ɡɚɞɚɱɢ
ɉɭɫɬɶ U – ɧɟɤɨɬɨɪɨɟ ɦɧɨɠɟɫɬɜɨ; m,nN; ɞɥɹ ɥɸɛɵɯ i 1, …, m, j 1, …, n: ai, bj, cijŽU,
ɦɧɨɠɟɫɬɜɚ ai, bj, cij ɹɜɥɹɸɬɫɹ ɤɨɧɟɱɧɵɦɢ.
Ɉɛɨɡɧɚɱɢɦ ɱɟɪɟɡ Bul(U) ɱɚɫɬɢɱɧɨ ɭɩɨɪɹɞɨɱɟɧɧɨɟ ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɩɨɞɦɧɨɠɟɫɬɜ ɦɧɨɠɟɫɬɜɚ U,
ɭɩɨɪɹɞɨɱɟɧɧɨɟ ɩɨ ɨɬɧɨɲɟɧɢɸ ɜɤɥɸɱɟɧɢɹ Ž. ɗɬɨ ɱɚɫɬɢɱɧɨ ɭɩɨɪɹɞɨɱɟɧɧɨɟ ɦɧɨɠɟɫɬɜɨ ɛɭɞɟɦ ɧɚɡɵɜɚɬɶ ɜ
ɞɚɥɶɧɟɣɲɟɦ ɛɭɥɟɚɧɨɦ.
Ɋɚɫɫɦɨɬɪɢɦ ɧɚɞ ɛɭɥɟɚɧɨɦ Bul(U) ɡɚɞɚɱɭ ɨ ɧɚɯɨɠɞɟɧɢɢ ɫɪɟɞɢ (mun)-ɦɚɬɪɢɰ X = (xij) ɫ ɜɟɤɬɨɪɨɦ
ɫɬɪɨɱɟɱɧɵɯ ɫɭɦɦ (ɨɛɴɟɞɢɧɟɧɢɣ) a (a1, …, am) ɢ ɜɟɤɬɨɪɨɦ ɫɬɨɥɛɰɨɜɵɯ ɫɭɦɦ b (b1, …, bn) ɬɨɣ, ɤɨɬɨɪɚɹ
ɞɨɫɬɚɜɥɹɟɬ ɦɢɧɢɦɭɦ ɮɭɧɤɰɢɨɧɚɥɭ
m
n
z = ™ ™ | cij ˆ xij |.
i=1 j=1
ɉɨ ɚɧɚɥɨɝɢɢ ɫ ɨɛɵɱɧɵɦ ɥɢɧɟɣɧɵɦ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɟɦ (ɇɟɫɬɟɪɨɜ, 1971; ɉɨɥɭɧɢɧ, 1975)
ɧɚɡɨɜɟɦ ɬɚɤɭɸ ɡɚɞɚɱɭ ɬɪɚɧɫɩɨɪɬɧɨɣ. Ɉɱɟɜɢɞɧɨ, ɱɬɨ ɤɪɢɬɟɪɢɟɦ ɪɚɡɪɟɲɢɦɨɫɬɢ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɧɚɞ
ɛɭɥɟɚɧɨɦ ɹɜɥɹɟɬɫɹ ɜɵɩɨɥɧɟɧɢɟ ɪɚɜɟɧɫɬɜɚ a1‰…‰am b1‰…‰bn.
Ɉɬɦɟɬɢɦ ɧɟɤɨɬɨɪɵɟ ɨɫɨɛɟɧɧɨɫɬɢ ɩɨɫɬɚɜɥɟɧɧɨɣ ɡɚɞɚɱɢ, ɧɚ ɨɫɧɨɜɟ ɤɨɬɨɪɵɯ ɛɭɞɟɦ ɫɬɪɨɢɬɶ ɟɟ
ɪɟɲɟɧɢɟ.
1) ɉɪɢ ɤɨɧɟɱɧɵɯ ai, bj, cij ɦɧɨɠɟɫɬɜɨ ɪɟɲɟɧɢɣ S ɫɢɫɬɟɦɵ ɭɪɚɜɧɟɧɢɣ
425
Ʉɭɦɚɪɨɜ ȼ.Ƚ. Ɋɟɲɟɧɢɟ ɨɞɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɧɚɞ ɦɧɨɠɟɫɬɜɚɦɢ
­x11‰…‰ x1n = a1
°… … … …
°xm1‰…‰ xmn = am
®
°x11‰…‰ xm1 = b1
°… … … …
¯x1n‰…‰ xmn = bn
(1)
ɹɜɥɹɟɬɫɹ ɤɨɧɟɱɧɵɦ, ɢ ɩɪɢ ɜɵɩɨɥɧɟɧɢɢ ɪɚɜɟɧɫɬɜɚ a1‰…‰am b1‰…‰bn ɦɚɤɫɢɦɚɥɶɧɵɦ ɷɥɟɦɟɧɬɨɦ ɜ ɷɬɨɦ
ɦɧɨɠɟɫɬɜɟ ɹɜɥɹɟɬɫɹ ɜɟɤɬɨɪ
(D11, …, D1n, D21, …, D2n, …, Dm1, …, Dmn),
(2)
ɝɞɟ ɞɥɹ ɥɸɛɵɯ i 1, …, m, j 1, …, n: Dij ai ˆ bj.
2) Ɉɩɬɢɦɚɥɶɧɨɟ ɪɟɲɟɧɢɟ ɡɚɞɚɱɢ (ɪɟɲɟɧɢɟ, ɞɨɫɬɚɜɥɹɸɳɟɟ ɮɭɧɤɰɢɨɧɚɥɭ z ɦɢɧɢɦɭɦ) ɫɥɟɞɭɟɬ
ɢɫɤɚɬɶ ɫɪɟɞɢ ɦɢɧɢɦɚɥɶɧɵɯ ɷɥɟɦɟɧɬɨɜ ɜɟɪɯɧɟɣ ɩɨɥɭɪɟɲɟɬɤɢ (S, Ž) (Ȼɢɪɤɝɨɮ, 1984).
3) Ʌɸɛɨɣ ɦɢɧɢɦɚɥɶɧɵɣ ɷɥɟɦɟɧɬ ɱɚɫɬɢɱɧɨ ɭɩɨɪɹɞɨɱɟɧɧɨɝɨ ɦɧɨɠɟɫɬɜɚ (S, Ž) ɦɨɠɟɬ ɛɵɬɶ ɩɨɥɭɱɟɧ
ɢɡ ɜɟɤɬɨɪɚ (2) ɢɫɤɥɸɱɟɧɢɟɦ ɢɡ ɧɟɤɨɬɨɪɵɯ ɟɝɨ ɤɨɨɪɞɢɧɚɬ ɨɩɪɟɞɟɥɟɧɧɵɯ ɷɥɟɦɟɧɬɨɜ.
Ⱦɥɹ ɩɪɨɫɬɨɬɵ ɞɚɥɶɧɟɣɲɢɯ ɪɚɫɫɭɠɞɟɧɢɣ ɜɟɤɬɨɪ (x11, …, x1n, x21, …, x2n, …, xm1, …, xmn) ɛɭɞɟɦ
ɡɚɞɚɜɚɬɶ ɦɚɬɪɢɰɟɣ
§x11 … x1n·
X = ¨x21 … x2n ¨
¨… … … ¨,
©xm1 … xmn¹
ɚ ɩɪɢ ɪɟɲɟɧɢɢ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɛɭɞɟɦ ɩɨɥɶɡɨɜɚɬɶɫɹ ɬɚɛɥɢɰɟɣ ɜɢɞɚ
c11
c1n
x11
x1n = a1
(3)
cm1
cmn
xm1
xmn
||
b1
= a m,
||
bn
ɜ ɤɨɬɨɪɨɣ ɨɛɴɟɞɢɧɟɧɵ ɜɫɟ ɟɟ ɞɚɧɧɵɟ.
3. Ɋɟɲɟɧɢɟ ɡɚɞɚɱɢ
Ⱦɚɥɟɟ ɫɪɚɡɭ ɩɪɢɜɟɞɟɦ ɚɥɝɨɪɢɬɦ ɪɟɲɟɧɢɹ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɧɚɞ ɛɭɥɟɚɧɨɦ, ɨɛɨɫɧɨɜɵɜɚɹ ɩɪɢ
ɧɟɨɛɯɨɞɢɦɨɫɬɢ ɟɝɨ ɷɬɚɩɵ ɩɨ ɯɨɞɭ ɢɡɥɨɠɟɧɢɹ.
1) ȼɵɹɫɧɟɧɢɟ ɪɚɡɪɟɲɢɦɨɫɬɢ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɩɭɬɟɦ ɩɪɨɜɟɪɤɢ ɜɵɩɨɥɧɟɧɢɹ ɪɚɜɟɧɫɬɜɚ
a1‰…‰am b1‰…‰bn.
2) ȼɧɟɫɟɧɢɟ ɜ ɬɪɚɧɫɩɨɪɬɧɭɸ ɬɚɛɥɢɰɭ ɦɚɤɫɢɦɚɥɶɧɨɝɨ ɷɥɟɦɟɧɬɚ ɱɚɫɬɢɱɧɨ ɭɩɨɪɹɞɨɱɟɧɧɨɝɨ
ɦɧɨɠɟɫɬɜɚ (S, Ž): X (xij) (ai ˆ bj)mun.
3) ȼɵɞɟɥɟɧɢɟ ɜ ɦɧɨɠɟɫɬɜɚɯ xij ɷɥɟɦɟɧɬɨɜ, ɤɨɬɨɪɵɟ ɧɟɥɶɡɹ ɨɬɛɪɨɫɢɬɶ, ɩɭɬɟɦ ɩɪɨɫɦɚɬɪɢɜɚɧɢɹ ɫɬɪɨɤ
ɢ ɫɬɨɥɛɰɨɜ ɬɪɚɧɫɩɨɪɬɧɨɣ ɬɚɛɥɢɰɵ. ɗɥɟɦɟɧɬ D ɦɧɨɠɟɫɬɜɚ xij ɛɭɞɟɬ ɜɵɞɟɥɟɧ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɨɧ
ɧɟ ɫɨɞɟɪɠɢɬɫɹ ɛɨɥɶɲɟ ɧɢ ɜ ɤɚɤɨɦ ɞɪɭɝɨɦ ɦɧɨɠɟɫɬɜɟ i-ɨɣ ɫɬɪɨɤɢ ɢɥɢ j-ɝɨ ɫɬɨɥɛɰɚ ɦɚɬɪɢɰɵ X.
ɉɪɢɦɟɪɵ
c11
c12
c13
= {1, 2, 3}
{1}
{2}
{3}
c21
c23
c22
= {4, 5}
{5}
{4}
‡
c32
c33
a) c31
= {1, 4, 6}
{1}
{4}
‡
c41
c42
c43
= {7}
{7}
{7}
‡
||
||
||
{1, 7}
{2, 5, 7}
{3, 4, 6}
426
ȼɟɫɬɧɢɤ ɆȽɌɍ, ɬɨɦ 7, ʋ3, 2004 ɝ.
ɫɬɪ.425-428
ȼ ɷɬɨɦ ɩɪɢɦɟɪɟ ɜɫɟ ɷɥɟɦɟɧɬɵ ɨɤɚɡɵɜɚɸɬɫɹ ɜɵɞɟɥɟɧɧɵɦɢ. ɗɬɨ ɨɡɧɚɱɚɟɬ, ɱɬɨ ɫɭɳɟɫɬɜɭɟɬ ɬɨɥɶɤɨ
ɨɞɧɚ ɦɚɬɪɢɰɚ ɫ ɡɚɞɚɧɧɵɦɢ ɜɟɤɬɨɪɚɦɢ ɫɬɪɨɱɟɱɧɵɯ ɢ ɫɬɨɥɛɰɨɜɵɯ ɫɭɦɦ ɢ ɢɦɟɧɧɨ ɨɧɚ ɹɜɥɹɟɬɫɹ
ɨɩɬɢɦɚɥɶɧɵɦ ɪɟɲɟɧɢɟɦ.
{1,3}
{2}
{1}
{2,5,6}
{8,9}
{1,7}
{6}
{4}
{7,8}
{4}
{7}
{3}
{5,8}
||
{1,3,7}
{2}
{9}
‡
{3,7}
‡
{4,8,9}
{6}
{1}
{2,5}
{4,8}
{7}
ɛ)
{3}
{9}
‡
{7}
{8}
||
{4,8,9}
{3,5}
||
{2,3,5}
{3,5,7}
{1,5}
{1,6}
{1,8}
{2,5,8}
{8}
{5}
{6}
{2,6,7}
{5,8}
||
{1,5,6,8}
= {1,2,5,9}
= {1,4,7,8}
= {2,4,7,8,9}
= {6,9}
= {3,5,7,8}
4) ȿɫɥɢ ɜɫɟ ɷɥɟɦɟɧɬɵ ɦɧɨɠɟɫɬɜ xij ɬɚɛɥ. 3 ɨɤɚɡɵɜɚɸɬɫɹ ɜɵɞɟɥɟɧɧɵɦɢ, ɬɨ ɪɟɲɟɧɢɟ, ɩɨɫɬɪɨɟɧɧɨɟ ɜ
ɬɚɛɥɢɰɟ, ɹɜɥɹɟɬɫɹ ɨɩɬɢɦɚɥɶɧɵɦ. ȼ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ ɩɟɪɟɯɨɞɢɦ ɤ ɫɥɟɞɭɸɳɟɦɭ ɩɭɧɤɬɭ ɚɥɝɨɪɢɬɦɚ 5).
Ⱦɨɤɚɠɟɦ ɞɚɥɟɟ ɬɨɬ ɮɚɤɬ, ɱɬɨ ɤɚɠɞɵɣ ɧɟɜɵɞɟɥɟɧɧɵɣ ɧɚ ɬɪɟɬɶɟɦ ɷɬɚɩɟ ɷɥɟɦɟɧɬ D ɪɚɫɩɨɥɚɝɚɟɬɫɹ ɜ
ɬɚɛɥɢɰɟ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:
D …D …D
. .
.
D …D …D
. .
.
D …D ...D
ɩɪɢɱɟɦ ɤɨɥɢɱɟɫɬɜɨ ɫɬɪɨɤ ɢ ɫɬɨɥɛɰɨɜ ɜ ɬɚɤɨɦ ɢɯ ɪɚɫɩɨɥɨɠɟɧɢɢ ɧɟ ɦɟɧɶɲɟ ɞɜɭɯ.
ɉɭɫɬɶ ɧɟɤɨɬɨɪɵɣ ɧɟɜɵɞɟɥɟɧɧɵɣ ɷɥɟɦɟɧɬ D ɜɫɬɪɟɱɚɟɬɫɹ ɜ k ɫɬɨɥɛɰɚɯ ɫ ɧɨɦɟɪɚɦɢ j1, …, jk ɢ l
ɫɬɪɨɤɚɯ ɫ ɧɨɦɟɪɚɦɢ i1, …, il.
ȿɫɥɢ ɯɨɬɹ ɛɵ ɨɞɧɨ ɢɯ ɱɢɫɟɥ l ɢɥɢ k ɪɚɜɧɨ 1, ɬɨ D ɞɨɥɠɟɧ ɛɵɥ ɛɵ ɛɵɬɶ ɜɵɞɟɥɟɧɧɵɦ, ɱɬɨ
ɩɪɨɬɢɜɨɪɟɱɢɬ ɟɝɨ ɜɵɛɨɪɭ. Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, k, lt2.
ɉɪɢ k,lt2 ɫɨɞɟɪɠɚɧɢɟ ɜ ɦɧɨɠɟɫɬɜɚɯ xpq (p
i1, …, il; q
j1, …, jk) ɷɥɟɦɟɧɬɚ D ɫɥɟɞɭɟɬ ɢɡ
,
…,
il ɢ ɤɚɠɞɨɦ ɢɡ ɫɬɨɥɛɰɨɜ j1, …, jk
ɩɨɫɬɪɨɟɧɢɹ ɨɩɨɪɧɨɝɨ ɪɟɲɟɧɢɹ. Ɍɚɤ ɤɚɤ k,lt2, ɬɨ ɜ ɤɚɠɞɨɣ ɢɡ ɫɬɪɨɤ i1
ɷɥɟɦɟɧɬ D ɫɨɞɟɪɠɢɬɫɹ, ɩɨ ɤɪɚɣɧɟɣ ɦɟɪɟ, ɜ ɞɜɭɯ ɦɧɨɠɟɫɬɜɚɯ ɢ ɩɨɷɬɨɦɭ ɨɤɚɡɵɜɚɟɬɫɹ ɧɟɜɵɞɟɥɟɧɧɵɦ ɧɢ ɜ
ɨɞɧɨɦ ɢɡ ɦɧɨɠɟɫɬɜ xpq.
ɉɪɨɜɟɞɟɧɧɨɟ ɞɨɤɚɡɚɬɟɥɶɫɬɜɨ ɩɨɡɜɨɥɹɟɬ ɞɥɹ ɤɚɠɞɨɝɨ ɧɟɜɵɞɟɥɟɧɧɨɝɨ ɷɥɟɦɟɧɬɚ D ɨɩɪɟɞɟɥɢɬɶ
ɦɚɬɪɢɰɭ D(D) (dpq)luk, ɝɞɟ dpq |cpq ˆ{D}|, p i1, …, il; q j1, …, jk. Ɉɬɦɟɬɢɦ, ɱɬɨ ɷɥɟɦɟɧɬɵ ɦɚɬɪɢɰɵ D(D)
ɦɨɝɭɬ ɩɪɢɧɢɦɚɬɶ ɥɢɲɶ ɞɜɚ ɡɧɚɱɟɧɢɹ: 0 ɢɥɢ 1.
5) Ɉɩɬɢɦɢɡɚɰɢɹ ɪɟɲɟɧɢɹ, ɩɨɫɬɪɨɟɧɧɨɝɨ ɜ ɬɚɛɥ. 3.
Ⱦɥɹ ɨɩɬɢɦɢɡɚɰɢɢ ɪɟɲɟɧɢɹ ɧɟɨɛɯɨɞɢɦɨ ɜɵɹɫɧɢɬɶ, ɢɡ ɤɚɤɢɯ ɦɧɨɠɟɫɬɜ ɫɥɟɞɭɟɬ ɭɞɚɥɢɬɶ
ɧɟɜɵɞɟɥɟɧɧɵɟ ɷɥɟɦɟɧɬɵ, ɚ ɜ ɤɚɤɢɯ ɨɫɬɚɜɢɬɶ, ɱɬɨɛɵ, ɜɨ-ɩɟɪɜɵɯ, ɫɨɯɪɚɧɢɬɶ ɫɬɪɨɱɟɱɧɵɟ ɢ ɫɬɨɥɛɰɨɜɵɟ
ɫɭɦɦɵ, ɚ, ɜɨ-ɜɬɨɪɵɯ, ɭɦɟɧɶɲɢɬɶ ɧɚɫɤɨɥɶɤɨ ɷɬɨ ɜɨɡɦɨɠɧɨ ɡɧɚɱɟɧɢɟ ɮɭɧɤɰɢɨɧɚɥɚ z.
Ⱦɨɝɨɜɨɪɢɦɫɹ ɭ ɷɥɟɦɟɧɬɚ dpq ɦɚɬɪɢɰɵ D(D) ɫɬɚɜɢɬɶ ɡɧɚɤ "+", ɟɫɥɢ ɜ ɫɨɨɬɜɟɬɫɬɜɭɸɳɟɦ ɦɧɨɠɟɫɬɜɟ
xpq ɦɵ ɪɟɲɢɥɢ ɨɫɬɚɜɢɬɶ ɷɥɟɦɟɧɬ D.
Ɍɚɤ ɤɚɤ ɞɥɹ ɥɸɛɵɯ i 1, …, m, j 1, …, n:
| cij ˆ xij | = ™ | cij ˆ{r} |,
(4)
rxij
ɬɨ ɩɪɢ dpq 0 ɨɫɬɚɜɥɟɧɢɟ ɜ ɫɨɨɬɜɟɬɫɬɜɭɸɳɟɦ xpq ɷɥɟɦɟɧɬɚ D ɧɟ ɜɥɢɹɟɬ ɧɚ ɡɧɚɱɟɧɢɟ ɮɭɧɤɰɢɨɧɚɥɚ. ȿɫɥɢ ɠɟ
dpq 1, ɬɨ ɩɪɢ ɨɫɬɚɜɥɟɧɢɢ ɜ ɦɧɨɠɟɫɬɜɟ xpq ɷɥɟɦɟɧɬɚ D ɫɨɨɬɜɟɬɫɬɜɭɸɳɟɟ ɫɥɚɝɚɟɦɨɟ ɜ ɩɪɚɜɨɣ ɱɚɫɬɢ
ɪɚɜɟɧɫɬɜɚ (4) ɪɚɜɧɨ 1. ɉɨɷɬɨɦɭ ɡɚɞɚɱɚ ɨ ɪɚɰɢɨɧɚɥɶɧɨɦ ɭɞɚɥɟɧɢɢ ɧɟɜɵɞɟɥɟɧɧɵɯ ɷɥɟɦɟɧɬɨɜ ɫɜɨɞɢɬɫɹ ɤ
ɡɚɞɚɱɟ ɨ ɪɚɫɫɬɚɧɨɜɤɟ ɡɧɚɤɨɜ "+" ɭ ɷɥɟɦɟɧɬɨɜ ɦɚɬɪɢɰɵ D(D) ɬɚɤɢɦ ɨɛɪɚɡɨɦ, ɱɬɨɛɵ: 1) ɡɧɚɤ "+" ɛɵɥ ɜ
ɤɚɠɞɨɣ ɫɬɪɨɤɟ ɢ ɤɚɠɞɨɦ ɫɬɨɥɛɰɟ; 2) ɫɨ ɡɧɚɤɨɦ "+" ɛɵɥɨ ɦɢɧɢɦɚɥɶɧɨɟ ɱɢɫɥɨ ɟɞɢɧɢɰ.
ɉɨɫɥɟɞɧɹɹ ɡɚɞɚɱɚ ɪɟɲɚɟɬɫɹ ɞɨɜɨɥɶɧɨ ɩɪɨɫɬɨ. Ɋɚɫɫɬɚɜɢɦ ɡɧɚɤ "+" ɭ ɜɫɟɯ ɧɭɥɟɜɵɯ ɷɥɟɦɟɧɬɨɜ
ɦɚɬɪɢɰɵ D(D). Ⱦɚɥɟɟ ɩɨɫɬɭɩɚɟɦ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:
1) ȿɫɥɢ ɜɨ ɜɫɟɯ ɫɬɪɨɤɚɯ ɢ ɫɬɨɥɛɰɚɯ ɦɚɬɪɢɰɵ D(D) ɨɤɚɠɟɬɫɹ ɯɨɬɹ ɛɵ ɨɞɢɧ ɡɧɚɤ "+", ɬɨ ɡɚɞɚɱɚ ɨ
ɪɚɫɫɬɚɧɨɜɤɟ ɡɧɚɤɨɜ ɭ ɷɥɟɦɟɧɬɨɜ ɷɬɨɣ ɦɚɬɪɢɰɵ ɪɟɲɟɧɚ.
427
Ʉɭɦɚɪɨɜ ȼ.Ƚ. Ɋɟɲɟɧɢɟ ɨɞɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɧɚɞ ɦɧɨɠɟɫɬɜɚɦɢ
2) ȿɫɥɢ ɨɤɚɠɭɬɫɹ ɫɬɪɨɤɢ ɢ ɫɬɨɥɛɰɵ, ɜ ɤɨɬɨɪɵɯ ɧɟ ɛɭɞɟɬ ɧɢ ɨɞɧɨɝɨ ɡɧɚɤɚ "+" (ɷɬɨ ɨɡɧɚɱɚɟɬ, ɱɬɨ ɜ
ɷɬɢɯ ɫɬɪɨɤɚɯ ɢ ɫɬɨɥɛɰɚɯ ɫɬɨɹɬ ɨɞɧɢ ɟɞɢɧɢɰɵ), ɬɨ ɨɱɟɜɢɞɧɨ, ɡɧɚɤ "+" ɫɥɟɞɭɟɬ ɩɨɫɬɚɜɢɬɶ ɭ ɷɥɟɦɟɧɬɨɜ,
ɫɬɨɹɳɢɯ ɧɚ ɩɟɪɟɫɟɱɟɧɢɢ ɷɬɢɯ ɫɬɪɨɤ ɢ ɫɬɨɥɛɰɨɜ.
3) ȿɫɥɢ ɛɟɡ ɡɧɚɤɚ "+" ɨɤɚɠɭɬɫɹ ɬɨɥɶɤɨ ɫɬɪɨɤɢ ɢɥɢ ɬɨɥɶɤɨ ɫɬɨɥɛɰɵ, ɬɨ ɡɧɚɤ "+" ɫɬɚɜɢɦ ɭ ɨɞɧɨɝɨ ɢɡ
ɢɯ ɷɥɟɦɟɧɬɨɜ (ɜɫɟ ɪɚɜɧɨ ɤɚɤɨɝɨ).
ɉɪɢɦɟɪɵ
§0+ 1 1· §1 1 1+ 1· §0+ 0+ 1 1 1·
°1 1 0+», ¨1 0+ 1 0+¨, ¨1 0+ 1+ 0+ 1¸.
©1 0+ 1¹ ¨1 1 1+ 1¨ ¨1 0+ 1 1 1¸
©0+ 1 1 0+¹ ©0 1 1 0+ 1+¹
5.1) Ⱦɥɹ ɤɚɠɞɨɝɨ ɧɟɜɵɞɟɥɟɧɧɨɝɨ ɷɥɟɦɟɧɬɚ D ɜɵɩɢɫɵɜɚɟɦ ɦɚɬɪɢɰɭ D(D) ɢ ɪɚɫɫɬɚɜɥɹɟɦ ɜ ɧɟɣ ɡɧɚɤɢ ɩɨ
ɨɩɢɫɚɧɧɨɦɭ ɜɵɲɟ ɚɥɝɨɪɢɬɦɭ.
5.2) Ⱦɥɹ ɤɚɠɞɨɝɨ ɧɟɜɵɞɟɥɟɧɧɨɝɨ ɷɥɟɦɟɧɬɚ D ɢɫɤɥɸɱɚɟɦ ɢɡ ɦɧɨɠɟɫɬɜ xpq ɷɥɟɦɟɧɬɚ D,
ɫɨɨɬɜɟɬɫɬɜɭɸɳɢɯ ɷɥɟɦɟɧɬɚɦ ɦɚɬɪɢɰɵ D(D) ɛɟɡ ɡɧɚɤɚ "+". ɉɟɪɟɯɨɞɢɦ ɤ ɩɭɧɤɬɭ 4) ɚɥɝɨɪɢɬɦɚ.
ɂɡ ɚɥɝɨɪɢɬɦɚ ɪɟɲɟɧɢɹ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɧɚɞ ɛɭɥɟɚɧɨɦ ɫɥɟɞɭɟɬ, ɱɬɨ ɟɫɥɢ ɬɪɚɧɫɩɨɪɬɧɚɹ ɡɚɞɚɱɚ
ɪɚɡɪɟɲɢɦɚ, ɬɨ
min z = max [ |{i:Dai ˆ ˆ cij}|,|{j:Dbj ˆ ˆ cij}| ].
j:Dbj
i:Dai
ɉɪɢɦɟɪ. ɇɚɣɞɟɦ ɨɩɬɢɦɚɥɶɧɨɟ ɪɟɲɟɧɢɟ, ɞɥɹ ɬɚɛɥɢɰɵ ɛ). ɂɦɟɟɦ,
§1 0+·
§1 1+·
§1 0+·
D(1) = ¨
¸, D(5) = ¨
¸, D(1) = ¨1+ 1 ¸.
©0+ 1¹
©0+ 1¹
©1 0+¹
{2}
{1,3}
{3}
‡
{2,5,6}
{8,9}
{7,8}
{7}
{6}
{1}
‡
{3}
‡
= {1,4,7,8}
‡
{5}
‡
{7}
{5,8}
{8}
{2}
{9}
{3,7}
= {1,2,5,9}
{2,5,8}
{4,8,9}
‡
{1,5}
{1,6}
{4}
{7}
{4}
{2}
{4}
{1,7}
{6}
{3,5,7}
{9}
{6}
= {6,9}
{8}
= {3,5,7,8}
{2,6,7}
{3,5}
= {2,4,7,8,9}
||
||
||
||
{1,3,7}
{4,8,9}
{2,3,5}
{1,5,6,8}
Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɨɩɬɢɦɚɥɶɧɵɦ ɪɟɲɟɧɢɟɦ ɹɜɥɹɟɬɫɹ ɦɚɬɪɢɰɚ
§ ‡
{9} {2} {1,5}·
X* = ¨{1,7} {4} ‡ {8} ¸,
¨ {7} {4,8,9} {2} ‡ ¸
©{3,7} ‡ {3,5} {8} ¹
ɚ ɦɢɧɢɦɚɥɶɧɨɟ ɡɧɚɱɟɧɢɟ ɮɭɧɤɰɢɨɧɚɥɚ, ɡɚɞɚɧɧɨɝɨ ɬɚɛɥɢɰɟɣ ɛ), ɪɚɜɧɨ 2.
4. Ɂɚɤɥɸɱɟɧɢɟ
ȼ ɪɚɛɨɬɟ ɨɩɢɫɚɧ ɦɟɬɨɞ ɪɟɲɟɧɢɹ ɩɪɨɫɬɟɣɲɟɣ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
ɧɚɞ ɦɧɨɠɟɫɬɜɚɦɢ. ɉɨ ɚɧɚɥɨɝɢɢ ɫ ɧɢɦ ɦɨɠɧɨ ɫɮɨɪɦɭɥɢɪɨɜɚɬɶ ɚɥɝɨɪɢɬɦɵ ɪɟɲɟɧɢɹ ɛɨɥɟɟ ɫɥɨɠɧɵɯ
ɬɪɚɧɫɩɨɪɬɧɵɯ ɡɚɞɚɱ. ȼɫɟ ɷɬɢ ɡɚɞɚɱɢ ɢɦɟɸɬ ɟɫɬɟɫɬɜɟɧɧɨɟ ɷɤɨɧɨɦɢɱɟɫɤɨɟ ɩɪɢɦɟɧɟɧɢɟ ɢ ɩɨɡɜɨɥɹɸɬ
ɨɩɬɢɦɢɡɢɪɨɜɚɬɶ ɦɧɨɝɢɟ ɷɤɨɧɨɦɢɱɟɫɤɢɟ ɩɪɨɰɟɫɫɵ.
Ʌɢɬɟɪɚɬɭɪɚ
Lieby Paulette. Extremal problems in finite sets. Bul. Austral. Math. Soc., N 1, p.175-176, 2000.
Ȼɢɪɤɝɨɮ Ƚ. Ɍɟɨɪɢɹ ɪɟɲɟɬɨɤ. Ɇ., ɇɚɭɤɚ, 566 c., 1984.
ɇɟɫɬɟɪɨɜ ȿ.ɉ. Ɍɪɚɧɫɩɨɪɬɧɚɹ ɡɚɞɚɱɚ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ. Ɇ., Ɍɪɚɧɫɩɨɪɬ, 216 c., 1971.
ɉɨɥɭɧɢɧ ɂ.Ɏ. Ʉɭɪɫ ɦɚɬɟɦɚɬɢɱɟɫɤɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ. Ɇɢɧɫɤ, ȼɵɫɲɷɣɲɚɹ ɲɤɨɥɚ, 380 c., 1975.
428
Документ
Категория
Без категории
Просмотров
4
Размер файла
65 Кб
Теги
решение, над, множества, одной, линейного, задачи, программирование
1/--страниц
Пожаловаться на содержимое документа