• Вступ
  • I. Опис задачі цілочислового програмування
  • II. Метод гілок і меж
  • III.
  • §1.1 реккурентная обчислення A (
  • Список літератури
  • Додаток 1
  • Додаток 2


  • Дата конвертації23.03.2017
    Розмір34.39 Kb.
    Типкурсова робота

    Скачати 34.39 Kb.

    Застосування методу гілок і меж для задач календарного планування

    Фінансової академії при Уряді РФ

    Кафедра «Математика і фінансові програми»

    Курсова робота з дисципліни

    «Метод гілок і меж в дослідженні операцій»

    Застосування методу гілок і меж для задач календарного планування

    Москва 2011


    зміст

    Вступ

    I. Опис задачі цілочислового програмування

    II. Метод гілок і меж

    §1. Опис методу гілок і меж

    §2. Алгоритм дії методу гілок і меж

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

    §4. Приклад використання методу гілок і меж

    III. Застосування методу гілок і меж для задач календарного планування

    §1. Алгоритм розв'язання задачі трьох верстатів методом гілок і меж

    k) і умова домінування

    §1.2 Спосіб конструювання варіантів послідовностей s і обчислення оцінок D (s) для кожного з них.

    §2. Приклад використання методу гілок і меж в задачі трьох верстатів

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

    додатки

    Додаток 1

    Додаток 2

    додаток 3


    Вступ

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

    Будуть розглянуті приклади, як простого застосування методу, так і для завдань календарного планування (буде розглянуто задачу про трьох верстатах).

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


    I. Опис задачі цілочислового програмування

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

    Завдання лінійного цілочисельного програмування формується таким чином: знайти таке рішення (план) X = (x 1, x 2,..., x n), при якому лінійна функція

    (1)

    приймає максимальне або мінімальне значення при обмеженнях:

    = B i, . (2)

    х j ³ 0, . (3)

    x j ÎZ, . (4).


    II. Метод гілок і меж

    §1. Опис методу гілок і меж

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

    Метод гілок і меж полягає в наступному: безліч припустимих рішень (планів) деяким способом розбивається на підмножини, кожне з яких цим же способом знову розбивається на підмножини. Процес триває до тих пір, поки не отримано оптимальне цілочисельне рішення вихідної завдання.

    §2. Алгоритм дії методу гілок і меж

    Спочатку знаходимо, наприклад, симплекс-методом оптимальний план завдання без урахування целочисленности змінних. Нехай їм є план X 0. Якщо серед компонент цього плану немає дробових чисел, то тим самим знайдено шукане рішення даного завдання і F max = F (X 0).

    Якщо ж серед компонент плану X 0 є дробові числа, то X 0 не задовольняє умові целочисленности і необхідно здійснити упорядкований перехід до нових планів, поки не буде знайдено рішення задачі. Покажемо, як це можна зробити, попередньо зазначивши, що F (X 0) ³F (X) для будь-якого подальшого плану X в зв'язку зі збільшенням кількості обмежень.

    Припускаючи, що знайдений оптимальний план X 0 не задовольняє умові целочисленности змінних, тим самим вважаємо, що серед його компонент є дробові числа. Нехай, наприклад, змінна прийняла в плані X 0 дробове значення. Тоді в оптимальному целочисленном плані її значення буде принаймні або менше або дорівнює найближчого меншого цілого числа , Або більше або дорівнює найближчого більшого цілого числа . Визначаючи ці числа, знаходимо симплекс-методом вирішення двох завдань лінійного програмування:

    Знайдемо рішення задач лінійного програмування (5) і (6). Очевидно, тут можливий один з наступних чотирьох випадків:

    1. Одне із завдань нерозв'язна, а інша має цілочисельний оптимальний план. Тоді цей план і значення цільової функції на ньому і дають рішення вихідної завдання.

    2. Одне із завдань нерозв'язна, а інша має оптимальний план, серед компонент якого є дробові числа. Тоді розглядаємо друге завдання і в її оптимальному плані вибираємо одну з компонент, значення якої дорівнює дробовому числу, і будуємо два завдання, аналогічні завданням (5) і (6).

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

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

    3.2. Якщо ж значення цільової функції більше на плані, серед компонент якого є дробові числа, то слід взяти одне з таких чисел і для завдання, план якої розглядається, необхідно побудувати два завдання, аналогічні (5) і (6).

    4. Обидва завдання можна розв'язати, і серед оптимальних планів обох завдань є дробові числа. Тоді обчислюємо значення цільової функції на даних оптимальних планах і розглядаємо ту із завдань, для якої значення цільової функції є найбільшим. В оптимальному плані цього завдання вибираємо одну з компонент, значення якої є дробовим числом, і будуємо два завдання, аналогічні (5) і (6).

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

    Таким чином, описаний вище ітераційний процес може бути представлений у вигляді деякого дерева, на якому вихідна вершина відповідає оптимальному плану Х 0 завдання (1) - (3), а кожна з'єднана з нею гілкою вершина відповідає оптимальним планам завдань (5) і (6 ). Кожна з цих вершин має свої розгалуження. При цьому на кожному кроці вибирається та вершина, для якої значення функції є найбільшим. Якщо на певному етапі буде отримано план, який має цілочисельні компоненти, і значення функції на ньому виявиться більше або дорівнює, ніж значення функції в інших можливих для розгалуження вершинах, то даний план є оптимальним планом вихідної задачі цілочислового програмування і значення цільової функції на ньому є максимальним .

    Отже, процес знаходження рішення задачі цілочислового програмування (1) - (4) методом гілок і меж включає наступні основні етапи:

    1. Знаходять рішення задачі лінійного програмування (1) - (3).

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

    3. Знаходять рішення задач (5) і (6), які виходять з завдання (1) - (3) в результаті приєднання додаткових обмежень.

    4. У разі необхідності складають додаткові обмеження для змінної, значення якої є дробовим, формулюють завдання, аналогічні завданням (5) і (6), і знаходять їх рішення.

    Ітераційний процес продовжують до тих пір, поки не буде знайдена вершина, відповідна целочисленному планом завдання (1) - (4) і така, що значення функції в цій вершині більше або дорівнює значенню функції в інших можливих для розгалуження вершинах.

    Описаний вище метод гілок і меж має більш просту логічну схему розрахунків, ніж метод Гоморі. Тому в більшості випадків для знаходження вирішення конкретних завдань цілочисельного програмування з використанням ЕОМ застосовується саме цей метод.

    §4. Приклад використання методу гілок і меж

    Як приклад до методу гілок і меж розглянемо функцію z = 4х 1 + х 2 + 1®max (7) при обмеженнях:


    (8). x 1, x 2 ÎZ, (9).

    Нехай Х 0 = (0; 0), z 0 = 1 - «оптимальне» [1] рішення (10) .Виполнім 1-й етап загального алгоритму та знайдемо за допомогою симплекс-методу, а потім і двоїстого симплекс-методу (див . Додаток 1) X 1, виходячи з обмежень (8). Отже, X 1 = (3; 0,5; 0; 1; 0; 2,5), z 1 = 13,5 (11). Так як z 1 дробове, то «оптимальним» так і залишається план Х 0,

    Згідно 2-му пункту нашого плану, складемо 2 нових системи обмежень для (7):

    (12) і (13).

    Виконаємо 3-й пункт алгоритму. Для початку, вирішимо завдання (7), (12) за допомогою табличного процесора MicrosoftExcel (див. Додаток 2) і отримаємо X 2 = (2; 1) [2] , z 2 = 10 (14). Так як z 2 ≥ z 0, «оптимальним» стає план Х 0.

    Вирішимо задачу (7), (13). З останнього рівняння очевидно, що x 2 = 0. Звідси випливає, що x 1 = 3 (максимально можливе).Тоді Х 3 = (3; 0), z 3 = 13 (15), а отже, даний план є оптимальним (тепер уже без лапок).

    Нам не довелося виконувати 4-й пункт нашого алгоритму в зв'язку з тим, що оптимальне рішення знайдено, змінні цілочисельні. До того ж, всі необхідні моменти рішення вже були показані в пунктах 1-3.

    Приклад, в якому все складається не так просто, наведений у Додатку 3.

    календарне планування програмування


    III. Застосування методу гілок і меж для задач календарного планування

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

    Для того, щоб з'ясувати області застосування даного методу і ознайомитися з практичною його формою, ми звернемося до задачі трьох верстатів [3] , як до класичного прикладу.

    §1. Алгоритм розв'язання задачі трьох верстатів методом гілок і меж

    Заданиnдеталей d i (i = 1, 2, ..., n), послідовно оброблюваних на трьох верстатах R 1, R 2, R 3, причому технологічні маршрути всіх деталей однакові. Позначимо a i, b i, c i - тривалість обробки деталей d i на першому, другому і третьому верстатах відповідно.

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

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

    Обозначімs k = (i 1, i 2,..., i k) - деяку послідовність черговості запуску довжиною k (1 £ k £ n) і A (s k), В (s k), С (s k) - час закінчення обробки послідовності деталей s k на першому, другому і третьому верстатах відповідно.

    Необхідно знайти таку послідовність s опт, що

    С (s опт) = min З (s). (16)

    §1.1 реккурентная обчислення A ( s k), В (s k), C (s k) і умова домінування

    Покажемо, якомога рекуррентно обчислювати A (s k), В (s k), С (s k). Нехай s k +1 = (s k, i k + i), т. Е. Послідовність деталей s k +1 отримана з деталей s k з додаванням ще однієї деталі i k +1. тоді:

    A (s k +1) = A (s k) + (17),

    В (s k +1) = max [A (s k +1); В (s k)] + (18),

    С (s k +1) = max [В (s k +1); С (s k)] + (19).

    Логіка виразів (17) - (19) очевидна, особливо якщо розглянути задачу двох верстатів.

    Для завдання трьох верстатів можна використовувати наступне правило домінування:

    Якщо s - деяка початкова послідовність, а - Підпослідовність, утворена з s перестановкою деяких символів, то варіант s домінує над , Коли виконуються наступні нерівності:

    А (s) £ А ( ), В (s) £ В ( ), С (s) £ С ( ) (20),


    причому хоча б одне з них виконується як суворе нерівність.

    §1.2 Спосіб конструювання варіантів послідовностей s і обчислення оцінок D (s) для кожного з них

    Спосіб конструювання варіантів послідовностей s і обчислення оцінок D (s) для кожного з них полягає в наступному:

    Нехай є початкова підпослідовність s. Тоді обчислюються величини:

    d C (s) = С (s) + , (21)

    d B (s) = В (s) + + , (22)

    d A (s) = A (s) + + (23),

    де J (s) - безліч символів, що утворюють послідовність s.

    За оцінку критерію З (s) для варіанту s можна прийняти величину

    D (s) = max {d A (s), d B (s), d C (s)} (24).

    Тоді хід розв'язання задачі трьох верстатів можна наступній формальної схемою:

    1) Нульовий крок. Завдання безлічі G (0), утворюється усіма можливими послідовностями (s = 0).

    Обчислення оцінки для безлічі G 0:

    D (0) = max {d A (0), d B (0), d C (0)} (25), де


    ; ; (26).

    2) Перший крок. ОбразованіемножествG 1 (1), G 2 (1),..., G n (1), подмножествоG k визначається всіма послідовностями з початком i k (k, ..., n).

    Обчислення оцінок. Оцінку для послідовності s k визначають зі співвідношення (24), т. Е. D (s k) = max {d A (s k), d B (s k), d C (s k)}; k = 1, ..., n. (27).

    Вибір варіанту для продовження. З усіх підпослідовностей, побудованих на попередньому кроці, вибирають найбільш перспективну послідовність s k з меншою оцінкою, т. Е. D (s k (1)) = minD (s j (1)). (28)

    Розгалуження. Вибравши найбільш перспективний варіант послідовності s k (1), розвивають його побудовою всіх можливих підпослідовностей довжиною 2 з початком s k (1) виду s k +1 (2) = (s k (1), j), де j не входить в s k.

    Обчислення оцінок виробляють відповідно до співвідношеннями (21), (22), (23).

    3) k-й крок. Припустимо, що вже проведено kшагов, в результаті чого побудовані варіанти s 1 (k), s 2 (k),..., s k (k), а саме підпослідовності довжиною k.

    Вибираємо найперспективніший варіант s S (k) такою, що

    D (s s (k)) = minD (s j (k)).

    Безліч G s (k) розбиваємо на (n - k) підмножин, кожне з яких утворюється додаванням до послідовності s s (k) деякого елемента i k +1 такого, що i k +1 .

    оцінка визначається відповідно до співвідношеннями (21) - (24).

    В результаті будуємо дерево варіантів такого вигляду: вершина Про відповідає s = 0, вершини першого рівня G 1 (1), G 2 (1)..., G n (1) відповідають послідовностям довжиною 1, т. Е. S 1 ( 1) = 1, s 2 (1) = 2, ..., s n (1) = п і т. д. Кожна кінцева вершина відповідає послідовності максимальної довжини n.

    Ознака оптимальності. Якщо s v (n) відповідає кінцевій вершині дерева, причому оцінка найменша з оцінок всіх вершин, то s v (n) - шуканий варіант.

    §2. Приклад використання методу гілок і меж в задачі трьох верстатів

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

    Вирішимо задачу трьох верстатів, умови якої наведені в табл. 1:

    Таблиця 1

    тривалість операцій деталь
    1 2 3 4 5

    a i

    b i

    c i

    2

    3

    4

    5

    2

    4

    1

    1

    2

    3

    4

    2

    3

    5

    2

    1) Нульовий крок. s = 0.

    d A (s = 0) = A (0) + + = 0 + 14 + 3 = 17;

    d B (s = 0) = В (0) + + = 0 + 15 + 2 = 17;

    d C (s = 0) = С (0) + = 14.


    тоді

    Δ (s = 0) = max {17, 17,14} = 17.

    2) Перший крок. Конструюємо всі можливі послідовності довжиною 1

    s 1 (1) = 1; s 2 (1) = 2; s 3 (1) = 3; s 4 (1) = 4; s 5 (1) = 5.

    знаходимо:

    d A (1) = A 1 + + = 14 + 3 = 17;

    d B (1) = В 1 + + = 5 + 12 + 2 = 19;

    d C (1) = С 1 + = 9 + 10 = 19.

    Звідки Δ (1) = max {17, 19, 19} = 19.

    Аналогічно визначаємо Δ (2), Δ (3), Δ (4), Δ (5).

    3) Другий крок. Серед безлічі підпослідовностей довжиною 1, s 1 (1) = 1, s 2 (1) = 2, ..., s 5 (1) = 5 вибираємо найбільш перспективну s = 1, для якої величина оцінки-прогнозу Δ (s) виявляється найменшою. Далі розвиваємо її, конструюючи можливі варіанти довжиною 2, т. Е. (1.2), (1.3), (1.4), (1.5).

    Для кожного з цих варіантів знову визначаємо оцінки за формулами (21) - (24).

    Процес обчислень продовжуємо аналогічно.

    Процес побудови дерева варіантів наведено на рис. 1.


    Малюнок 1

    Кожній кінцевої вершині дерева варіантів буде відповідати повна послідовність s = i 1, i 2,, .i n. Якщо для деякої такої вершини величина оцінки Δ (s) не перевищує величини оцінок для всіх інших вершин, то ця оцінка визначає шуканий оптимальний варіант. В іншому випадку розбиваємо більш перспективний варіант з найкращою оцінкою.

    Кінцева вершина визначає варіант (послідовність) = 3, 1, 5, 2, 4 з найкращою оцінкою Δ = 20. Тому даний варіант є оптимальним.

    Безпосередньою перевіркою переконуємося, що час обробки всієї послідовності деталей для цього варіанта збігається зі значенням оцінки-прогнозу і є мінімальним:

    .


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

    1. Акулич І.Л. Математичне програмування в прикладах і завданнях. М., Вища школа, 1993.

    2. Гончаренко В.М. «Математичні методи і моделі операцій. Керівництво вирішення завдань ». М., Фінансова Академия, 2006.

    3. Зайченко Ю.П. Дослідження операцій. Київ, Вища школа, 1975.

    4. Кузнєцов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування. М., Вища школа, 1980.

    5. Шкурба В.В. Завдання трьох верстатів. М., Наука, 1976.

    Додаток 1

    Рішення завдання

    z = 4х 1 + х 2 +1 ® max при обмеженнях:

    симплекс-методом:

    базис b i x 1 x 2 x 3 x 4 x 5 x 6
    x 3 4 1 2 1 0 0 0
    x 4 12 3 2 0 1 0 0
    x 5 3 1 0 0 0 1 0
    x 6 3 0 1 0 1 0 1
    z 1 -4 -1 0 0 0 0
    x 2 2 0,5 1 0,5 0 0 0
    x 4 8 2 0 -1 1 0 0
    x 5 3 1 0 0 0 1 0
    x 6 1 -0,5 0 -0,5 0 0 1
    z 3 -3,5 0 1 0 0 0
    x 1 4 1 2 1 0 0 0
    x 4 0 0 -2 -2 1 0 0
    x 5 -1 0 -2 -1 0 1 0
    x 6 3 0 1 0 0 0 1
    z 17 0 7 4,5 0 0 0
    x 1 3 1 0 0 0 1 0
    x 4 1 0 0 -1 1 -1 0
    X 2 0,5 0 1 0,5 0 -0,5 0
    x 6 2,5 0 0 -0,5 0 0,5 1
    z 3,5 0 0 1,5 0 3,5 0

    z * = 13,5, Х 1 * = (3; 0,5; 0; 1; 0; 2,5).


    Додаток 2

    Рішення завдання z = 4х 1 + х 2 +1 ® max при обмеженнях:

    за допомогою табличного процесора MicrosoftExcel.


    додаток 3

    Як приклад застосування методу гілок і меж наведемо пошук оптимального значення функції Z = Зх 1 + х 2 ® max при обмеженнях:


    4x l + Зх 2 <18,

    x 1 + 2x 2 £ 6,

    0 £ x 1 £ 5,

    0 £ x 2 £ 4,

    х 1, x 2 - цілі числа.

    Рішення

    За нижню межу лінійної функції приймемо, наприклад, її значення в точці (0,0), тобто Z 0 = Z (0; 0) = 0.

    I етап. Вирішуючи задачу симплекс-методом, отримаємо Z max = 13,5 при Х 1 * = (4,5; 0; 0; 1,5; 0,5; 4); так як перша компонента х 1 * подрібнена, то з області рішення виключається смуга, яка містить дробове оптимальне значення х 1 *, тобто 4 <х 1 <5. Тому завдання 1 розбивається на два завдання 2 і 3.


    завдання 2

    Z = 3x 1 + x 2 → max

    при обмеженнях:


    4x l + Зх 2 <18

    x 1 + 2x 2 £ 6

    0 £ x 1 £ 4

    0 £ x 2 £ 4

    х 1, x 2 - цілі числа.

    завдання 3

    Z = 3x 1 + x 2 → max

    при обмеженнях:


    4x l + Зх 2 <18

    x 1 + 2x 2 £ 6

    5 £ x 1 £ 5

    0 £ x 2 £ 4

    х 1, x 2 - цілі числа.

    Список завдань: 2 і 3. Нижня межа лінійної функції не змінилася: Z 0 = 0.

    II етап. Вирішуємо (за вибором) одну із завдань списку, наприклад завдання 3 симплекс-методом.

    Отримаємо, що умови завдання 3 суперечливі.

    III етап. Вирішуємо задачу 2 симплекс-методом. Отримаємо Z max = 12 2/3 при X 3 * = (4; 2/3; 0; 2/3; 0; 10/3). Хоча Z (X 3 *) = 12 2/3> Z 0 = 0, як і раніше зберігається Z 0 = 0, бо план нецілочисельне. Так як х 2 * - дробове число, з області рішень виключаємо смугу 0 2 <1 і завдання 2 розбиваємо на два завдання 4 і 5.

    завдання 4

    Z = 3x 1 + x 2 → max

    при обмеженнях:

    4x l + Зх 2 <18

    x 1 + 2x 2 £ 6

    0 £ x 1 £ 4

    0 £ x 2 £ 0

    х 1, x 2 - цілі числа.


    завдання 5

    Z = 3x 1 + x 2 → max

    при обмеженнях:

    4x l + Зх 2 <18

    x 1 + 2x 2 £ 6

    0 £ x 1 £ 4

    1 £ x 2 £ 4

    х 1, x 2 - цілі числа.

    Список завдань: 4 і 5. Значення Z 0 = 0.

    IV етап. Решаемзадачу 4 симплекс-методом.

    Отримаємо Zmax = 12 пріX 4 * = (4; 0; 2; 2; 0; 0). Завдання виключаємо зі списку, але при цьому меняемZ 0; Z 0 = Z (X 4 *) = 12, бо план Х 4 * цілочисельний.

    V етап. Вирішуємо задачу 5 симплекс-методом.

    Отримаємо Z max = 12,25 при X 5 * = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не змінюється, тобто Z 0 = 12, бо план X 5 * нецілочисельне. Так як х 1 * - дробове, з області рішень виключаємо смугу 3 1 <4, і завдання 5 розбивається на два завдання: 6 і 7.


    завдання 6

    Z = 3x 1 + x 2 → max

    при обмеженнях:


    4x l + Зх 2 <18

    x 1 + 2x 2 £ 6

    0 £ x 1 £ 3

    1 £ x 2 £ 4

    х 1, x 2 - цілі числа.


    завдання 7

    Z = 3x 1 + x 2 → max

    при обмеженнях:


    4x l + Зх 2 <18

    x 1 + 2x 2 £ 6

    4 £ x 1 £ 4

    1 £ x 2 £ 4

    х 1, x 2 - цілі числа.

    Список завдань: 6 і 7. Значення Z 0 = 12.

    VI етап. Вирішуємо одне із завдань списку, наприклад завдання 7, симплекс-методом. Отримаємо, що умови завдання 7 суперечливі.

    VII етап. Вирішуємо задачу 6 симплекс-методом. Отримаємо Z m a x = 10,5, при X 6 * = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так як, Z (X 6 *) = 10,5 0 = 12, то завдання виключається зі списку.

    Отже, список завдань вичерпаний і оптимальним цілочисельним рішенням вихідної задачі буде X * = Х 4 * = (4; 0; 2; 2; 0; 0), а оптимум лінійної функції Z max = 12.


    [1] «Оптимальним» будемо називати план, оптимальний на даний момент рішення.

    [2] Природно, без введення і обчислення змінних штучного базису.

    [3] «про три станкак».


    Головна сторінка


        Головна сторінка



    Застосування методу гілок і меж для задач календарного планування

    Скачати 34.39 Kb.