Курсова робота: Потоки на мережі

План

Вступ    3

  1. Постановка задачі    5
  2. Задача про найкоротший шлях.    8
  3. Метод Мінті    9
  4. Задача про максимальний потік.    13
  5. Метод Форда-Фалкерсона    15

Висновки    21

Список використаної літератури    22

 

Вступ

Задачі пошуку маршруту в мережі є одними з найпоширеніших задач потокового типу, що використовуються в транспорті, і включають вирішення таких питань як визначення найкоротших відстаней на заданій мережі доріг, побудову найкоротшої мережі доріг, визначення максимального потоку в мережі, розрахунок пропускної здатності транспортної мережі та визначення “вузьких місць” в ній тощо.

Задача обчислення максимального потоку в мережі є класичною задачею оптимізації, алгоритми рішення якої розроблялися протягом останніх 50 – 60 років. Методи рішення застосовуються у транспортних, комунікаційних, електричних мережах, при моделюванні різноманітних фізичних та хімічних процесів тощо. Початковим підходом до розв’язку задачі знаходження максимального потоку було застосування симплекс-методу лінійного програмування. У 1956 році Фордом та Фалкерсоном для рішення цієї задачі було запропоновано використання орієнтованої мережі та ітераційного псевдополіноміального алгоритму, що дозволило поліпшити оцінку алгоритму знаходження максимального потоку.

Задачі потокового типу відносяться до задач лінійного програмування та можуть бути розв’язані за допомогою симплекс-методу, але через значну розмірність відповідних задач лінійного програмування ця можливість є лише принциповою. Тому розробляються спеціальні алгоритми їх розв’язання відповідно до структури задачі. Знання теоретичних основ та володіння потоковими алгоритмами дозволяє ефективно розв’язувати різноманітні практичні задачі. Розв’язання потокової задачі полягає у знаходженні значень функції потоку, що протікає від джерела до витоку мережі і забезпечує екстремальне значення функції цілі для всіх дуг мережі (джерело t – це вузол мережі, в який потік втікає із зовнішнього середовища, а витік s – це вузол мережі, з якого потік витікає в зовнішнє середовище).

Отже, тема даного дослідження є досить актуальною, адже при розв’язанні потокових задач необхідно володіти специфічними методами знаходження розв’язку. Метою дослідження буде освоєння методів Мінті та Форда-Фалкерсона, виявлення їх особливостей та можливостей.

  1. Постановка задачі

Графом називається впорядкована пара g={I,U}, де I={…,i,…,j,…} — непорожня множина вершин, U={(i,j): i,jI} — множина впорядкованих пар, що називаються дугами. При цьому вершина i дуги (i,j) називається її початком, а j — її кінцем.

Геометрично граф зображується точками (множина вершин I) та лініями зі стрiлками (множина дуг U), що з’єднують деякі пари цих точок. На графіку зображено граф, для якого

I = {1,2,3,4,5}, U = {(1,2),(1,3),(2,1),(2,4),(4,3),(4,5),(5,2)}.


Рис. 1

Вище наведене означення орієнтованого графа, коли суттєвою є орієнтація зв’язку між вершинами. Якщо ж орієнтація зв’язку є несуттєвою, то від понять “дуга” та “орієнтований граф” переходять до понять “ребро” та “неорiєнтований граф”. Точнiше, неорiєнтованим графом називається впорядкована пара g={I,U}, де I — множина вершин, а U — множина невпорядкованих пар [i,j], де i,jI, що називаються ребрами. Геометрично ребра зображуються лініями, що з’єднують відповідні вершини.

Граф g називається скiнченним, якщо скiнченними є множини I та U.

Шляхом на графі g називається послідовність дуг u1,…,um (us=(is,js), s=1,…,m), початок кожної з яких, починаючи з другої, співпадає з кінцем попередньої, тобто is+1 = js, s=1,…,m–1. Зрозумiло, що шлях, який з’єднує вершини i1 та it можна задати послідовністю вершин, через які він проходить. На рис. 1 послідовність дуг (1,2), (2,4), (4,5) формує шлях, що з’єднує вершини 1 та 5. Цей же шлях можна задати послідовністю вершин (1,2,4,5).

Ланцюгом на графі g називається послідовність ребер u1,…,um (us=[is,js], s=1,…,m), в якій у кожного ребра, починаючи з другого, одна з вершин співпадає з однією з вершин попереднього, а друга — з якою-небудь вершиною наступного ребра. На рис. 1 ребра [1,3], [3,4], [4,5] утворюють ланцюг, який можна задати i послідовністю вершин [1,3,4,5].

Якщо початкова вершина шляху (ланцюга) співпадає з кінцевою, то маємо контур (цикл).

Мережею називається граф, елементам якого поставлені у відповідність деякі параметри. Елементами графа вважаються його вершини, дуги, або більш складні конструкції, утворені з вказаних елементарних.

Побудуємо мережу таким чином:

1) кожній вершині iI поставимо у відповідність число di, що називається її інтенсивністю. Вершина i називається джерелом, якщо di>0, стоком, якщо di<0, i нейтральною, якщо di=0;

2) кожній дузі (i,j)U поставимо у відповідність числа rij та cij, що називаються, відповідно, функцією пропускної спроможності та функцією вартості.

На практиці величини di часто інтерпретуються як об’єми виробництва (di>0) або споживання (di<0) деякого однорідного продукту в пункті (вершині) i. Величина rij визначає пропускну спроможність дуги (комунікації) (i,j), а величина cij, наприклад, собівартість транспортних перевезень по дузі (i,j).

Потоком (однорідним) в одержаній мережі називається сукупність величин xij, (i,j)U, що задовольняють умовам:

    (1)


    (2)

Спiввiдношення (1) називаються рівняннями збереження, або рівняннями неперервності. Фiзично вони означають, що різниця між величиною потоку, що виходить з вершини i та величиною потоку, що входить до неї, дорівнює її інтенсивності (рис. 2).


Рис. 2

Нехай VI. Множина U(V) дуг (i,j) таких, що iV, jV, називається розрізом мережі, тобто U(V) = {(i,j)U: iV, jV}.

Величина


називається пропускною спроможністю розрізу U(V).

Загальні умови існування потоку на мережі встановлюються такою теоремою, яку ми приводимо без доведення.

Теорема 1. Для того, щоб на мережі існував потік, необхідно i достатньо, щоб d(I)=0 i для довільної множини VI виконувалась умова d(V)≤r(V), де


Iншими словами, потік на мережі існує тоді i лише тоді, коли сумарна інтенсивність всіх вершин мережі дорівнює нулю, а сумарна інтенсивність будь-якої пiдмножини вершин не перевищує пропускної спроможності розрізу мережі, що породжується цією підмножиною.

Кожному потоку x = {xij, (i,j)U} поставимо у відповідність цільову функцію


Лiнiйна задача на мережі (або задача про оптимальний потік на мережі) полягає у пошуку допустимого потоку x на мережі, що мiнiмiзує цільову функцію L(x), тобто


Допустимий потік x називається оптимальним, якщо він доставляє мінімальне значення функції L(x).

Очевидно, що задача про оптимальний потік на мережі є частинним випадком ЗЛП i, отже, може бути розв’язана загальними методами лінійного програмування. Зрозумiло, що специфіка цієї задачі може суттєво використовуватися при розробці частинних, більш ефективних методів її розв’язування.

  1. Задача про найкоротший шлях.

    Розглянемо мережу, що визначається графом g, з означеною на U функцією вартості сij. Розглянемо також дві фіксовані вершини i1, is графа g та довільний шлях, що з’єднує i1 та is:

    I = I(i1,is) = ((i1,i2), (i2,i3),…, (is-1,is)) = (i1,i2,i3,…,is-1,is),     (4)

    де it I, t = {1,..,s}.

    Розглянемо функцію


    яка інтерпретується або як собівартість перевезення вантажу по шляху I, або як довжина шляху I. В останньому випадку cij — довжина дуги (i,j)U.

    Задача про найкоротший шлях (про вибір найбільш економного шляху) полягає в пошуку шляху (4), що мiнiмiзує цільову функцію (5). Шуканий шлях I* = arg min C(I) називається найкоротшим (оптимальним).

    З формальної точки зору сформульована задача є частинним випадком задачі про оптимальний потік. Для цього розглядається мережа, вершина i1 якої є джерелом одиничної інтенсивності, вершина is — стоком одиничної інтенсивності, решта вершин — нейтральні.

    Дугам приписуються необмежені пропускні спроможності, а собівартість перевезення по дузі дорівнює її довжині. Для потоку x = {xij, (i,j)U} у побудованій мережі


    Задача зводиться до знаходження потоку, що мiнiмiзує цільову функцію


    Легко зрозуміти, що для оптимального потоку x*={x*ij,(i,j)U} величини x*ij будуть рівними 1 або 0 в залежності від того, входить чи ні дуга (i,j) до найкоротшого шляху. Тому L(x*) дорівнює довжині найкоротшого шляху, що з’єднує вершини i1 та is.

    Для розв’язання задачі про найкоротший шлях розроблені методи, що враховують її специфіку. Одним з них є метод Мiнтi (метод позначок). Згiдно цього методу процес розв’язування задачі складається із скiнченного числа елементарних кроків, на кожному з яких позначаються вершини мережі та виділяються деякі її дуги.

    1. Метод Мiнтi

    Крок 1. Позначається вершина i1 (коренева вершина) позначкою , I(1) = {i1} — множина позначених вершин.

    Нехай після виконання r кроків є множина I(r) = {i1,…,iλ,…} позначених вершин iλ, кожній з яких поставлена у відповідність позначка .

    Крок (r+1). Розглянемо множину J(r)={…,iμ,…} непозначених вершин iμ: (iλ,iμ)U, iλI(r), iμJ(r), I(r)∩J(r)=. Для кожної з таких дуг (iλ,iμ) знаходимо суму

    ,

    виділяємо ті дуги, для яких ця сума мінімальна. При цьому з декількох дуг, що підлягають виділенню i закінчуються в одній i тій же вершині, виділяється лише одна (Рис. 3).


    Рис. 3

    Позначаємо кінці виділених дуг числом, що дорівнює мінімальному значенню . За рахунок позначених вершин множина I(r) розширюється до множини I(r+1)

    Вказаний процес продовжується до тих пір, поки серед позначених не з’явиться вершина is, або подальше позначення неможливе.

    За побудовою в кожній з позначених вершин (крім кореневої) закінчується одна виділена дуга. Тому рух від вершини is вздовж виділених дуг у напрямку, протилежному їх орієнтації, реалізується однозначно. Крiм того, початок виділеної дуги позначається раніше її кінця. Отже, послідовність виділених дуг, утворена в процесі руху від вершини is, утворює деякий шлях l*(i1,is) з початком в i1 та кінцем в is.

    Теорема 2. Побудований методом Мiнтi шлях l*(i1,is) є найкоротшим, що з’єднує вершини i1 та is, причому C(I*(i1,is)) =

    Доведення. Скористаємось методом математичної iндукцiї за номером кроку t, на якому позначена вершина it. При t=1 маємо it=i1 i теорема справедлива. Нехай твердження теореми виконується при t=r. Це значить, що є множина I(r) = {i1,…,iλ,…} вершин, позначених не більше, ніж за r кроків i шлях I*=I(i1,iλ), iλ
    I(r), — найкоротший з i1 в iλ, C(l*) = . Доведемо, що твердження теореми виконується при t=r+1. Нехай вершина is позначена на (r+1)-у кроцi. Покажемо, що шлях

    ,    (6)

    де , причому

        (7)

    де iα, iβ: iα I(r), iβ
    I(r), є найкоротшим з i1 в is.

    Крiм шляху l*(i1,is), визначеного співвідношенням (6), розглянемо шлях I(i1,is), що проходить через вершини iα та iβ (α≠s’), iαI(r) (див. рис. 4)


    Рис. 4

    Для довжин розглядуваних шляхів маємо такі оцінки:

    ,

    де перша з нерівностей випливає з припущення iндукцiї та C(I(iβ,is))≥0, а друга — з співвідношення (7).

    Зауваження.

    1. Сформульований вище алгоритм методу Мiнтi розрахований на знаходження єдиного найкоротшого шляху, що з’єднує вершини i1 та is. Щоб знайти всю множину найкоротших шляхів, на кожному кроцi слід виділяти всі дуги (iλ,iμ) з мінімальним показником навіть якщо декілька з них закінчуються в одній i тій же вершині. А при зворотному русі з вершини is вздовж виділених дуг у кожній з вершин слід розглядати всі можливі продовження.

    2. Насправді метод Мiнтi розв’язує більш загальну задачу: він знаходить найкоротший шлях з кореневої в кожну з позначених вершин.

    3. Якщо процес позначення вершин методом Мiнтi продовжувати до тих пір, поки не припиниться розширення множини позначених вершин, то буде розв’язана задача знаходження найкоротшого шляху з початкової вершини i1 у кожну позначену. Якщо при цьому деяка вершина iλ мережі не попала до числа позначених, то немає шляху з i1 в iλ.

    Приклад 1. Знайти найкоротший шлях з вершини 1 до решти вершин на мережі, зображеній на рис. 5.

    Крок 1. h1 = 0, I(1) = {1}.

    Крок 2. Розглядаються дуги (1,2), (1,3), що виходять з множини I(1). Обчислюємо величини h1 + c12 та h1 + c13, тобто

    h1 + c12 = 0 + 3 = 3,

    h1 + c13 = 0 + 2 = 2.

    Мiнiмальна з цих величин відповідає дузі (1,3). Дуга (1,3) виділяється, вершина 3 позначається числом 2 (h3 = 2). I(2) = {1,3}.


    Рис. 5

    Крок 3. Розглядаються дуги

    (1,2) → h1 + c12 = 3,

    (3,2) → h3 + c32 = 3,

    (3,5) → h3 + c35 = 5.

    Мiнiмальна з підрахованих величин відповідає дугам (1,2), (3,2). Видiлимо дугу (1,2), h2 = 3, I(3) = {1,2,3}.

    Крок 4. Розглядаються дуги

    (2,5) → h2 + c25 = 4,

    (2,8) → h2 + c28 = 4,

    (3,5) → h3 + c35 = 5.

    Видiляємо дуги (2,5), (2,8), h5 = 4, h8 = 4, I(4) = {1,2,3,5,8}.

    Крок 5. Розглядаються дуги

    (5,6) → h5 + c56 = 5,

    (8,7) → h8 + c87 = 5.

    Видiляємо дуги (5,6), (8,7), h6 = 5, h7 = 5, I(5) = {1,2,3,5,6,7,8}.

    Подальше позначення вершин методом Мiнтi неможливе. Повна множина позначених вершин I*={1,2,3,5,6,7,8}. Серед позначених відсутня вершина 4, тобто немає шляху з вершини 1 у вершину 4.

    Як приклад укажемо найкоротший шлях з вершини 1 у вершину 6. Це шлях l*(1,6) = (1,2,5,6). Знаходиться він переглядом виділених дуг від вершини 6 до вершини 1. При цьому C(l*(1,6)) = h6 = 5.

    1. Задача про максимальний потік.

    Ця задача, як i задача про найкоротший шлях, є частинним випадком задачі про оптимальний потік. Iз задачею про максимальний потік тісно пов’язана задача про мінімальний розріз мережі. Наведемо формулювання цих задач.

    Розглянемо мережу, що визначається графом g, яка має єдине джерело s, єдиний стік t та означену на множині U функцію пропускної спроможності rij. Нехай інтенсивність джерела ds = d. За теоремою існування потоку на мережі інтенсивність стоку має бути рівною dt = -d Допустимий потік для розглядуваної мережі визначається співвідношеннями:


    Задача про максимальний потік полягає у знаходженні максимального значення інтенсивності d, при якому в розглядуваній мережі існує потік. Потiк x*={x*ij,(i,j)U}, що відповідає максимальному значенню d* інтенсивності, називається максимальним потоком, а d* — величиною цього потоку.

    Розглянемо описану вище мережу. Розрізом мережі, що відокремлює s від t, називається множина дуг U(C)={(i,j)U: iC, jC}, де C — деяка множина вершин (CI) мережі, така, що sC, tC.

    Нагадаємо, що пропускна спроможність цього розрізу визначається звичайним чином:


    Приклад 2. Розглянемо мережу, зображену на рис. 6, де вершина 1 є джерелом, а вершина 6 — стоком. Нехай C = {1,2,3}, тоді U(C) = {(2,4),(2,5),(3,5)} — розріз, який відокремлює вершину 1 від вершини 6, що відповідає вибраній множині C. Пропускна спроможність цього розрізу

    r(C) = r24 + r25 + r35 = 5 + 2 + 1 = 8.


    Рис. 6

    Зрозумiло, що для кожної конкретної мережі вибір множини C повністю визначає пропускну спроможність розрізу. Розріз, що має найменшу пропускну спроможність, називається мінімальним. Задача пошуку такого розрізу називається задачею про мінімальний розріз.

    Виявляється, що сформульовані задачі є двоїстими i, як слід чекати, їх розв’язки тісно пов’язані між собою.

    1. Метод Форда-Фалкерсона

    Теорема 3 (Форда-Фалкерсона). Величина максимального потоку із s в t дорівнює пропускній спроможності мінімального розрізу, що відокремлює s від t.

    Зауважимо, що теорема тривіальна, якщо мережа складається з вершин та дуг, що утворюють єдиний шлях від s до t (див. рис. 7)


    Рис. 7

    У наведеному прикладі мінімальний розріз здійснює дуга (2,3). Її пропускна спроможність r23=2 визначає максимальну інтенсивність d*=2 допустимого для мережі потоку.

    Доведення. Нехай x*={x*ij,(i,j)U} — максимальний потік на мережі, що визначається графом g, d* — величина максимального потоку. Нехай U(C) — довільний розріз мережі, що відокремлює s від t, r(C) — його пропускна спроможність. За теоремою існування потоку d*≤r(C). Нам необхідно показати, що існує така множина C*, що


    Множина C*, що визначає мінімальний розріз, будується на основі потоку x* таким чином:

    s C*,

    якщо i C* та x*ij < rij, то j C*,     (9)

    якщо i C* та x*ki > 0, то i C*.

    Спочатку покажемо, що tC*. Вiд супротивного: нехай tC*. Iз означення (9) множини C* випливає, що будь-якi дві її вершини можна з’єднати ланцюгом. З’єднаємо вершини sC* та tC*:

    C=[s = i1, i2,…, im = t].     (10)

    Для цього ланцюга умови (9) можна переписати так:

    якщо для ребра


    то

    якщо для ребра


    то

    Нехай

    ,


    Покладемо


    Нехай


    Зрозумiло, що θ > 0. Змiнимо потік вздовж ланцюга C, збільшуючи його на θ уздовж ребер множини C+ i зменшуючи його на θ уздовж ребер множини C. У результаті одержимо допустимий потік величини d*+θ, що суперечить припущенню про максимальність потоку x*. Отже tC*.

    Покажемо, що d* = r(C*). Iз означення (9) множини C* випливає, що

    якщо iC*, jC*, (i,j) U, то x*ij = rij,

    якщо iC*, kC*, (k,i) U, то x*ki = 0.    (13)

    Запишемо співвідношення (8) при x = x* для iC*



    Пiдсумовуючи останні рівності по iC*, маємо


    Розглядаючи випадки j,kC* та j,kC*, з останньої рівності маємо:



    Другий та третій доданки у цій рівності взаємно знищуються i, приймаючи до уваги (13), одержуємо


    або r(С*) = d*.

    Наслiдок. Якщо дуга (i,j) входить до мінімального розрізу, то величина максимального потоку по цій дузі дорівнює її пропускній спроможності rij. При цьому кажуть, що потік насичує дугу.

    Для розв’язування задачі про максимальний потік Фордом та Фалкерсоном був розроблений метод, що носить їх ім’я.

    Згiдно теореми про максимальний потік та мінімальний розріз за відомим максимальним потоком x*={x*ij,(i,j)U} легко побудувати мінімальний розріз U(С*) (див. співвідношення (9)). Крiм того, якщо потік не є максимальним, то можливе його збільшення шляхом зміни потоку вздовж певного ланцюга. Ці факти лежать в основі методу Форда-Фалкерсона, що являє собою рекурентну процедуру, на кожному кроцi якої позначаються вершини або будується потік більшої величини.

    Алгоритм Форда-Фалкерсона розпочинає роботу з будь-якого допустимого потоку x0 (зокрема нульового) величини d0. Згiдно (9) для цього потоку визначається множина C0. Якщо tC0, то потік x0 є максимальним, в іншому випадку можна знайти θ0>0 та новий потік x1={x1ij, (i,j)U} величини d1=d00. Для нового потоку цей цикл операцій повторюється i т. д.

    Процеси визначення Ck та θk об’єднуються в один процес “розставлення позначок” вершин. Позначка μ(i) довільної вершини i складається з двох чисел Ni та θi. Ці числа означають, що вздовж деякого ланцюга, останнім ребром якого є [|Ni|,i], можна додатково доставити θi одиниць потоку з вершини s до вершини i.

    Дамо детальний виклад алгоритму, вважаючи, що відомий допустимий потік x (зокрема нульовий).

    Алгоритм Форда-Фалкерсона

    Крок 1 (процес розставлення позначок). На цьому кроцi кожна з вершин належить до одного з трьох типів:

  2. • непозначена,
  3. • позначена i непроглянута,
  4. • позначена i проглянута.

    Спочатку всі вершини непозначенi.

    Позначимо вершину s позначкою μ(s)=(+s,θs=∞), що означає: можна послати потік з вершини s у саму себе необмеженої величини.

    Тепер вершина s позначена i непроглянута.

    Взагалі, нехай j — позначена i непроглянута вершина, μ(j)=(+i,θj) або μ(j)=(−i,θj) — її позначка. Розглядаємо ще непозначенi вершини k: (j,k)U i xjk < rjk. Кожнiй з таких вершин приписуємо позначку μ(k)=(+j,θk), де θk = min{θj, rjk – xjk}. Розглядаємо ще непозначенi вершини k: (k,j)U, i xkj > 0. Кожна з таких вершин одержує позначку μ(k)=(–j,θk), де θk = min{θj, xkj}.

    Всі вершини k, які одержали позначки, тепер позначені i непроглянутi, а вершина j — позначена i проглянута.

    Продовжуємо приписувати позначки непозначеним вершинам до тих пір, поки або вершина t виявиться позначеною, або не можна буде позначити жодної вершини i вершина t виявиться непозначеною.

    У другому випадку існуючий потік x — максимальний, а множина позначених вершин C* визначає мінімальний розріз мережі.

    У першому випадку існуючий потік x на кроцi 2 можна збільшити.

    Крок 2 (збільшення потоку). Нехай μ(t)=(+k,θt), або μ(t)=(–k,θt) — позначка вершини t. Це означає, що існуючий потік з s в t можна збільшити на величину θt. Для цього в першому випадку замінюємо xkt на xktt, у другому — xtk замінюємо на xtk–θt.

    Переходимо до вершини k i виконуємо аналогічні операції, змінюючи величину потоку на ту ж величину θt. Продовжуємо ці дії, поки не досягнемо вершини s. Пiсля цього ліквідовуємо позначки всіх вершин i переходимо до кроку 1.

    Приклад 3. Знайти максимальний потік з вершини 1 у вершину 8 на мережі, зображеній на рис. 8.

    Процес розв’язування задачі продовжується на рисунках 9–10. Біля кожної з дуг вказані величини xij (rij), тобто потік, що проходить через цю дугу та її пропускна спроможність.

    Множина C*, що визначає мінімальний розріз, має вигляд C*={1,2,3,4,5}. Величина максимального потоку d* = 2.


    Рис. 8


    Рис. 9


    Рис. 10

    Висновки

    Під час виконання дослідження по даній темі було освоєно різні алгоритми розв’язування транспортних задач лінійного програмування. Задачі про потік на мережі є більш загальними, ніж інші транспортні задачі, тому потребували більш детального розгляду деяких означень, ознайомлення із додатковим матеріалом.

    Знання теоретичних основ та володіння потоковими алгоритмами дозволяє ефективно розв’язувати різноманітні практичні задачі. В тому числі і задачі на визначення найкоротших відстаней на заданій мережі доріг, побудову найкоротшої мережі доріг, визначення максимального потоку в мережі, розрахунок пропускної здатності транспортної мережі та визначення “вузьких місць” в ній тощо.

     

    Список використаної літератури

    1. Ашманов С.А. Линейное программирование. — М.: Наука, 1981. — 340 с.
    2. Вильямс Н. Н. Параметрическое программирование в экономике. — М.: Статистика, 1976.
    3. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. — М.: Наука, 1966. — 524 с.
    4. Гольштейн Е.Г., ЮдинД.Б. Задачи линейного программирования транспортного типа. — М.: Наука, 1969. — 382 с.
    5. Катренко А.В. Дослідження операцій. Підручник. –Л.: Магнолія-Плюс, 2005. -549 с.
    6. Кулян В. Р., Юнькова Е. А., Жильцов А. Б. Математическое программирование с элементами информационных технологий. — К.: МАУП, 2000. — 124 с.
    7. Ляшенко И.Н. и др. Линейное и нелинейное программирование. — К.: Вища шк., 1975. — 372 с.
    8. Мулен Э. Теория игр с примерами из математической экономики: Пер. с фр. — М.: Мир, 1985. — 200 с.
    9. Муртаф Б. Современное линейное программирование. — М.: Мир, 1984. — 224 с.
    10. Попов Ю.Д. Линейное и нелинейное программирование. — К., УМК ВО, 1988. — 188 с.
    11. Хедли Дж. Нелинейное и динамическое программирование. — М.: Мир, 1967. — 506 с.
    12. Химмельблау Д. Прикладное нелинейное программирование. — М.: Мир, 1975. — 534 с.

    Юдин Д.Б., Гольштейн Е.Г. Линейное программирование: теория, методы и приложения. — М.: Наука, 1969. — 424 с.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Потоки (263.3 KiB, Завантажень: 10)

завантаження...
WordPress: 23.14MB | MySQL:26 | 0,342sec