Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсова робота

Визначення потреби в робочій силі

Завдання

Підприємство складає шестимісячний план прийому робітників. Кожний новий робітник повинний пройти попереднє підготування тривалістю q міс., що містить у собі ф-годинну практику на майбутньому робочому місці, аналізовану як ф год. робочого часу. Навчений робітник може працювати до ф1 год. на місяць, а за необхідності - менше. На початку січня підприємство мало X0 досвідчених робітників. Встановлено, що приблизно p% навчених робітників звільняється за власним бажанням. Досвідчений робітник обходиться підприємству в C грн., а той, якого навчають, - у S грн. на місяць. Потреба підприємства в кількості робочих часів задана.

Визначити число робітників Xi, навчання яких має початися в місяці і.

Показник	№
	1
Q	0.6
Ф	60
ф1	150
X0	70
Р	10
C1	850
C2	450
Потреба підприємства в робочу часі:
січень	10000
лютий	8000
березень	10000
квітень	12000
травень	9000
червень	12000

Методи вирішення:

Гоморі-2, метод розгалужень та обмежень.

Математична модель

Математична модель складається з:

1. Цільової функції

де - к січні, лютому, березні, квітні, травні та червні відповідно.

2. Обчислення:

81

60

39

3. Умова цільової системи:

- результат повинен бути цілими.

Вступ

Необхідно визначити число робітників Xi, навчання яких має початися в місяці і. Підприємство складає шестимісячний план прийому робітників. Кожний новий робітник повинний пройти попереднє підготування тривалістю q міс., що містить у собі ф-годинну практику на майбутньому робочому місці, аналізовану як ф год. робочого часу. Навчений робітник може працювати до ф1 год. на місяць, а за необхідності - менше. На початку січня підприємство мало X0 досвідчених робітників. Встановлено, що приблизно p% навчених робітників звільняється за власним бажанням. Досвідчений робітник обходиться підприємству в C грн., а той, якого навчають, - у S грн. на місяць. Потреба підприємства в кількості робочих часів задана. Необхідно визначити число робітників Xi, навчання яких має початися в місяці і.

математичний гоморі програма алгоритм

Показник	№
	1
Q	0.6
Ф	60
ф1	150
X0	70
Р	10
C1	850
C2	450
Потреба підприємства в робочу часі:
січень	10000
лютий	8000
березень	10000
квітень	12000
травень	9000
червень	12000

1. Розробка математичної моделі та аналіз методів

Математична модель

Математична модель складається з:

1. Цільової функції

де - к січні, лютому, березні, квітні, травні та червні відповідно.

2. Обчислення:

81

60

39

Методи вирішення:

Гоморі-2, метод розгалужень та обмежень.

Даний курсовий проект запропоновано розв'язати двома методами цілочисленого ділення: метод Гоморі 2, який реалізується програмно та метод розгалуджень та обмежень, розрахунок яким відбувається вручну.

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

Суть методу Гоморі полягає у наступному:

· отримання першого опорного рішення з використанням звичайної симплекс таблиці або двоїстого симплекс методу;

· на основі максимальної дробної змінної формується нове обмеження, щоб відсікати дробну частину;

· Рішення нової системи розмірністю m+1, n+1 відбувається за допомогою двоїстого симплекс метода;

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

Формування обмеження: - {yi}=

Перерахунок нової модель відбувається за такими формулами:

{bi}, якщо j=0

, якщо Xj - ціле та {aij} >={b0}

{aij}, якщо {aij} <{b0}

aij, якщо Xj - не ціле та {aij} >{b0}

, якщо {aij} <{b0}

Гоморі 2, на відміну від Гоморі, майже завжди дає відповідь та відрізняється тим, що не на всі змінні накладаються обмеження.

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

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

Зміст методу полягає в наступному:

1. Знаходимо рішення задачі лінійного програмування без обліку цілочисельних змінних.

2. Складаємо додаткові обмеження на дробову компоненту плану.

3. Знаходимо рішення двох задач з обмеженнями на компоненту.

4. Будуємо в разі потреби додаткові обмеження, відповідно до

можливих чотирьох випадків одержуємо цілочисельний план, або

встановлюємо нерозв'язаність системи.

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

2. Розв'язок задачі за допомогою методу Гоморі 2

Алгоритм програми

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

Для цього потрібно привести цільову функцію до max (Якщо вона спрямована на мінімізацію, то знак цільової функції змінюється на «-»), а обмеження до рівнянь. В цілюву функцію ніякі змінні не додаються. Всі знаки замінюються на знак « =», враховуючи відповідні правила переведення моделей від звичайної моделі до її канонічного вигляду (вони відмінні від правил переводу до канонічного моделі при симплекс методі). Правила переводу є наступними: якщо обмеження має знак «<» то при переведенні до канонічного вигляду, то додається одну змінна; якщо - «>» то віднімається одна змінна; якщо знак «=» то ніякі змінні не додаються.

Наступним етапом буде записана двоїста задача, на основі якої будуть сформовані незалежні вектори за допомогою введення А0…Аn. Після чого вибираємо спряжений базис розмірності m:

· Вибираємо m-рівнянь

· Вирішуємо систему

· Підставляємо рішення в інші обмеження (якщо рішення інших обмежень задовольняє рівняння, то базис знайдено, в іншому випадку шукаємо далі).

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

· Від max А0 відсікається дробна частина та створюється нова змінна (таким чином розмірність задачі збільшується).

· Розрахунок всіх останніх елементів рядка відбувається за допомогою вище перечислених правил.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Розв'язок за допомогою Гоморі 2

(c) Koziy Alena…PNK-41

Rozmirnist zadachi: 6x12

-405x1-850x2->max

-144x1+1x7=-6850

-123x1-1x2+1x8=-6320

-102x1-1x2-1x3+1x9=-9790

-81x1-1x2-1x3-1x4+1x10=-13260

-60x1-1x2-1x3-1x4-1x5+1x11=-11730

-39x1-1x2-1x3-1x4-1x5-1x6+1x12=-16200

Ymova cilochusesnosti:

0 0 0 0 0 0 0 0 0 0 0 0

Z=-214245

X=(47.57 14344.79 0 0 0 0 0 13875.83 9406.88 4937.92 5468.96 0)

3. Розрахунок задачі методом «Розгалуджень та обмежень».

Даний алгоритм має такий опис.

Перша частина складає окремий модуль (simpl). В цьому модулі реалізовані такі процедури, як:

· зчитування з текстового файлу;

· переведення до канонічного виду;

· розрахунок симплекс - методу.

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

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

Наступною дією є перевірка умови цілочисельності. Якщо умова виконується і всі значення X є цілочисельними то одразу отримуємо оптимальне рішення. Якщо умова цілочисельності не виконується то необхідно вибрати значення X з найбільшою дробною частиною і сформувати два нових обмеження відносно відповідного значення х. Обмеження формуються по типу «менше меншого» та «більше більшого». Потім ці обмеження по черзі додаються в початковий файл і формується наступний рівень дерева (формується дві нові моделі.). Першим рівнем дерева є файл отриманий при першому виконанні програми. Після цього застосовується розроблений модуль (simpl). Отримані результати перевіряються. Коли буде отримане перше цілочисельне рішення, то воно запам'ятовується, як максимальне. Процес формування дерева буде завершений тоді, коли всі вузли одного рівня будуть або не мати рішення, або рішення нецілочисельне буде гірше отриманого цілочисельного.

Дерево формується наступним чином. Наявні відповідні рівні, кожен наступний формується при знаходженні нецілочисельного значення X. Кількість рівнів відповідно становить N. Кількість вузлів відповідно збільшується на кожному рівні вдвічі. Результати кожного з них на одному рівні перевіряються. Після чого при наявності ознаки кращого нецілочисельного рішення формується наступний рівень. Якщо рішення відсутнє або гірше, процес побудови завершується.

Ітерація розв'язку

Начальный файл forvetv.txt

Размерность задачи: 6x14

Канонический вид:

-405X1-850X2-4050X4-4050X6-4050X8-4050X10-4050X12-4050X14-> max

144X1 -1X3+ 1X4=6850

123X1+ 1X2 -1X5+ 1X6=6320

102X1+ 1X2+ 1X3+ 1X4 -1X7+ 1X8=9790

81X1+ 1X2+ 1X3+ 1X4 -1X9+ 1X10=13260

60X1+ 1X2+ 1X3+ 1X4+ 1X5 -1X11+ 1X12=11730

39X1+ 1X2+ 1X3+ 1X4+ 1X5+ 1X6 -1X13+ 1X14=1620

Итерация №1

Решение найдено

Задача 1

Задача-передующая 0

X=(89.378 0 6020.400 0 4673.467 0 5346.933 0 0 0 4326.533 0 12559.600 0)

Z=-36198.000

Итерация №53

Размерность задачи ЦЛП - 11 x 22

-405X1-850X2-4050X4-4050X6-4050X8-4050X10-4050X12-4050X14-40500X15-40500X18-40500X21 -> max

144X1 -1X3+ 1X4 = 6850

123X1+ 1X2 -1X5+ 1X6 = 6320

102X1+ 1X2+ 1X3+ 1X4 -1X7+ 1X8 = 9790

81X1+ 1X2+ 1X3+ 1X4 -1X9+ 1X10 = 13260

60X1+ 1X2+ 1X3+ 1X4+ 1X5 -1X11+ 1X12 = 11730

39X1+ 1X2+ 1X3+ 1X4+ 1X5+ 1X6 -1X13+ 1X14 = 1620

1X2+ 1X15 -1X16 = 3

1X3+ 1X17 = 6019

1X2+ 1X18 -1X19 = 1

1X3+ 1X20 = 6020

1X3+ 1X21 -1X22 = 6021

Решение найдено

Задача 53

Задача-передующая 26

Ограничение X2>=3

X=(89.364 3 6018.480 0 4674.827 0 5346.653 0 0 0 1.520 0 12561.520 0.188 0 11.500 1.187 1 2 0.520 1.187 1)

Z=-38742.601

Конечное решение

X(1)= 89

X(2)= 0

X(3)=6007

X(4)= 41

X(5)=4627.000

Z=-214245

Результати цільової функції співпадають.

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

4. Дослідження на чутливість

Приклад 1:

(c) Koziy Alena…PNK-41

Размерность задачи: 2x6

-0.00x1-0.00x2-25x3-25x5->max

2x1+3x2+1x3-1x4=6000

2x1+1x2+1x5-1x6=4000

Условие целочисленности:

1 1 1 1 1 1

Z=-250000

X=(0 0 6000 0 4000 0)

Приклад 2:

(c) Koziy Alena…PNK-41

Размерность задачи: 5x11

-17x1-20x2-22x3-25x4-28x5-30x6->max

-3x1-4x3-6x5+1x7=-10

-2x2-4x4-5x6+1x8=-6

1x1+1x2+1x9=5

+1x3+1x4+1x10=15

+1x5+1x6+1x11=15

Условие целочисленности:

1 1 1 1 1 1 1 1 1 1 1

Z=-106.00

X=(3.33 1.67 0 0 0 0.53 0 0 0 15 14.47)

Размерность задачи: 6x12

-17x1-20x2-22x3-25x4-28x5-30x6->max

1x1+1.33x3+2x5-0.33x7=3.33

+1x2-1.33x3-2x5+0.33x7+1x9=1.67

+0.53x3+0.80x4+0.80x5+1x6-0.13x7-0.20x8-0.40x9=0.53

+1x3+1x4+1x10=15

-0.53x3-0.80x4+0.20x5+0.13x7+0.20x8+0.40x9+1x11=14.47

-0.47x3-0.20x4-0.20x5-0.13x7-0.20x8-0.40x9+1x12=-0.47

Условие целочисленности:

1 1 1 1 1 1 1 1 1 1 1 0

Z=-106.67

X=(0 3.00 0 0 1.67 0 0 0 2.00 15 13.33 0.67)

Размерность задачи: 7x13

-17x1-20x2-22x3-25x4-28x5-30x6->max

1x1+0.00x3-2x4-2.50x6-0.00x7+0.50x8+1x9=2.00

+1x2-0.00x3+2x4+2.50x6+0.00x7-0.50x8=3.00

0.50x1-0.33x3-1x4-1x6-0.17x7+1x12=0.67

+1x3+1x4+1x10=15

-0.50x1-0.67x3+1x6+0.17x7+1x11=13.33

0.50x1+0.67x3+1x5-0.17x7=1.67

-0.50x1-0.33x3-0.17x7+1x13=-0.33

Условие целочисленности:

1 1 1 1 1 1 1 1 1 1 1 0 0

Z=-116.00

X=(0 3 0 0 2.00 0 2.00 0 2.00 15 13 1.00 0)

Висновок

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

Математична модель:

10 15

60 50 37 45 56 50 35 23 25 54 33 34 53 12 67 max

1 4 2 1 3 1 1 2 3 4 2 3 4 2 4 <600

2 2 1 3 1 1 1 2 3 4 3 4 3 2 4 <590

3 1 2 2 1 1 2 2 3 4 5 3 2 2 1 <760

2 1 2 2 2 3 1 2 3 4 2 1 3 2 1 <670

2 2 1 2 3 3 1 3 4 2 1 2 3 4 3 <500

2 3 4 5 2 4 4 3 2 1 2 3 2 3 4 <760

2 3 4 2 3 2 3 5 2 3 4 5 6 4 3 <560

3 2 4 3 5 4 3 4 5 3 4 5 6 4 3 <680

3 3 1 2 3 2 3 2 1 2 3 3 2 3 2 <690

2 1 2 3 3 4 5 5 4 3 2 3 4 4 5 >560

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

X = (10 10 60 10 10 0 0 0 0 50 0 0 0 0 0 0 0 0 10 0 0 45 0 0 0 0)

Z = 16030

Отже, зробимо висновок, що програма спрацьовує на великій розмірності.

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

1. Тах Х.А. Введение в исследование операций. 6-ое издание. М. 2010.

2. Бабич В.І. Конспект лекцій з дисципліни «Математичні методи дослідження операцій» 2012.

3. Зайченко Ю.П. Курс лекцій з дослідження операцій. Веб-сайт факультету «ІПСА» - http://iasa.org.ua

Размещено на Allbest.ru