Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Zj - сj ? 0 для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:

В оцінковому рядку третьої симплексної таблиці немає від'ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, що знайдено оптимальний план задачі:

(2.15)

або

Х* = (48; 118; 0; 0; 0; 0); (2.16)

.(2.17)

Перевіримо правильність рішення задачі за допомогою MS Excel (див.рис.2.1-2.3).

Рисунок 2.1

Рисунок 2.2

Рисунок 2.3

ЗАДАЧА 3

Побудувати двоїсту задачу до заданої та знайти її розв'язок. Використовуючи теореми двоїстості знайти розв'язок прямої задачі. Задана пряма задача має вигляд:

аналіз задача симплексний програмування

max Z = - 5x1 + 2x2;

Розв'язання

Двоїста задача утворюється за такими правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі - на визначення найменшого значення (min), і навпаки.

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

Двоїстою до задачі

max Z=c0 + (c, x),

Ax=b, x0,

(записаній у векторно-матричній формі) є

,

, y0,

де - матриця, транспонована до А; (с, x), (b, y) - скалярні добутки відповідних векторів.

Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція Z максимізується і в системі обмежень є нерівності, то їх слід звести до виду «». Тому перше обмеження задачі помножимо на (-1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max Z = - 5x1 + 2x2; (3.1)

(3.2)

За наведеними вище правилами складемо двоїсту задачу:

min F = - y1 + 5y2; (3.3)

(3.4)

Оскільки записані задачі симетричні (обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід'ємних значень), то будь-яку з них можна розв'язати симплекс-методом. Наприклад, визначимо спочатку оптимальний план прямої задачі. Для цього застосуємо алгоритм симплекс-методу.

1. max Z = - 5x1 + 2x2 + 0x3 + 0x4; (3.5)

(3.6)

2. Векторна форма запису системи обмежень має вигляд:

, (3.7)

де , , , , .

У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження.

3. Розширена задача лінійного програмування буде такою:

max Z = - 5x1 + 2x2 + 0x3 + 0x4 - Мx5; (3.8)

(3.9)

У цій задачі х4 та х5 - базисні змінні, а х1, х2, х3 - вільні. Нехай х1=х2=х3=0, тоді х4=5; х5=1.

Перший опорний план задачі:

X0=(0; 0; 0; 5; 1), Z0 = - M. (3.10)

4. Подальше розв'язування прямої задачі подано у вигляді симплексної таблиці:

З останньої симплекс-таблиці запишемо оптимальний план прямої задачі:

Х*=(0; 5/3; 2/3; 0), Zmax = 10/3. (3.11)

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

min F = max Z = 10/3. (3.12)

Компоненти вектора Y* (оптимальний план двоїстої задачі) визначимо за формулою:

, (3.13)

де та міститься в стовпчику «сбаз» останньої симплекс-таблиці;

. (3.14)

Матриця D- 1 також міститься в останній симплекс-таблиці у стовпчиках змінних «x5» та «x4», які утворювали початковий базис.

Отже,

, (3.15)

min F = - 10 + 52/3 = 10/3. (3.16)

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

Перевіримо правильність рішення прямої задачі за допомогою MS Excel (див.рис.3.1-3.3).

Рисунок 3.1

Рисунок 3.2

Рисунок 3.3

Перевіримо правильність рішення двоїстої задачі за допомогою MS Excel (див.рис.3.4-3.6).

Рисунок 3.4

Рисунок 3.5

Рисунок 3.6

ЗАДАЧА 4

Компанія контролює три фабрики А1, А2, А3, здатні виготовляти відповідно 150, 60 та 80 тис.од. продукції щотижня. Вона уклала договір із чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня доставляти відповідно 110, 40, 60 та 80 тис.од. продукції. Вартість транспортування 1 тис.од. продукції замовникам з кожної фабрики наведена в таблиці:

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

Розв'язання

4.1 Побудова математичної моделі

Нехай xij - кількість продукції, що перевозиться з і-ої фабрики до j-го замовника . Загальні витрати, пов'язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування 1 тис.од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Оскільки транспортна задача за умовою є збалансованою, закритою

,

то математична модель сформульованої задачі має вигляд:

min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + x32 ++ 4x33 +2x34 (4.1)

за умов:

(4.2)

4.2 Знаходження першого опорного плану задачі

Запишемо умови задачі у вигляді транспортної таблиці (табл.4.1) та складемо її перший опорний план у цій таблиці методом мінімальної вартості.

Таблиця 4.1

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

Z1 = 4110 + 540 + 160 + 140 + 240 = 820 (ум. од.).(4.3)

Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п'яти, а (m+n-1) = 3+4-1=6.

Для дальшого розв'язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зайняти будь-яку пусту клітинку, яка не утворює замкненого циклу із заповненими клітинами. Наприклад, заповнимо нулем клітинку А2В4. Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність методом потенціалів.

4.3 Перевірка опорного плану на оптимальність

На основі першої умови оптимальності ui + vj = cij складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:

 (4.4)

Записана система рівнянь є невизначеною, і один з її розв'язків дістанемо, узявши, наприклад, v4 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1=5, u2=2, u3=2, v1= - 1, v2= - 1, v3= - 1. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ? cij (для порожніх клітинок таблиці):

А1B2 : u1 + v2 = 5 + (-1) = 4 = 4; (4.5)

А1B3 : u1 + v3 = 5 + (-1) = 4 > 2; (4.6)

А2B1 : u2 + v1 = 2 + (-1) = 1 < 5; (4.7)

А2B2 : u2 + v2 = 2 + (-1) = 1 < 3; (4.8)

А3B1 : u3 + v1 = 2 + (-1) = 1 < 2; (4.9)

А3B3 : u3 + v3 = 2 + (-1) = 1 < 4. (4.10)

Умова оптимальності не виконується для клітинки А1B3. Порушення 13=(u1+v3)-c13 = 4 - 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки.

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

4.4 Перехід від одного опорного плану до іншого

Потрібно заповнити клітинку А1B3, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B3, та позначаємо вершини циклу почергово знаками «-» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B3 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «-». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «-».

У даному разі , тобто . Виконавши перерозподіл перевезень продукції згідно із записаними правилами, дістанемо такі нові значення: для клітинки А1B3 -- 40 тис.од.продукції, а для А2B3 - (60 - 40) = 20 тис.од., а для А2B4 - (0+40) = 40 тис.од. Клітинка А1B4 звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n+m - 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд (табл.4.2).

Таблиця 4.2

Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:

Z2 = 4110 + 240 + 120 + 240 + 140 + 240 = 740 (ум.од.). (4.11)

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

Таблиця 4.3

Визначимо загальну вартість витрат на транспортування продукції згідно з третім опорним планом:

Z3 = 490 + 260 + 260 + 220 + 140 + 220 = 720 (ум.од.). (4.12)

Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому:

. (4.13)

За оптимальним планом перевезень перший замовник отримує 90 тис.од. продукції з першої фабрики та 20 тис.од. -- з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис.од. продукції з третьої фабрики і т.д. При цьому загальна вартість перевезень всієї продукції є найменшою і становить 720 ум.од.

Перевіримо правильність рішення задачі за допомогою MS Excel (див.рис.4.1-4.3).

Рисунок 4.1

Рисунок 4.2

Рисунок 4.3

ЗАДАЧА 5

Дані про роздрібний товарообіг і доходи населення в умовних грошових одиницях в деякій країні за 1996-2007рр. представлені в табл.5.1.

Таблиця 5.1 - Роздрібний товарообіг і доходи населення

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

Розв'язання

5.1 Оцінка параметрів споживчої функції

Зв'язок між роздрібним товарообігом і доходом населення носить прямолінійний характер, тому споживча функція має вигляд [3]:

, (5.1)

де - роздрібний товарообіг;

- особисті доходи громадян;

- константа;

- кутовий коефіцієнт кореляції;

- стохастична складова (залишки).

Для оцінювання параметрів та в рівнянні (5.1) скористаємось методом найменших квадратів (МНК). Запишемо систему нормальних рівнянь [3]:

(5.2)

. (5.3)

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

, (5.4)

, (5.5)

де - моменти першого порядку;

- моменти другого порядку.

; (5.6)

; (5.7)

; (5.8)

;(5.9)

. (5.10)

Для зручності розрахунку моментів побудуємо таблицю 5.2.

Таблиця 5.2 - Проміжні розрахунки

; (5.11)

; (5.12)

;(5.13)

;(5.14)

;(5.15)

; (5.16)

.(5.17)

Таким чином, маємо споживчу функцію:

. (5.18)

5.2 Перевірка достовірності підібраної лінії регресії методом аналізу дисперсій за критерієм Фішера

Розрахуємо критерій Фішера [3]:

(5.19)

де - обґрунтована складова дисперсії;

- необґрунтована складова дисперсії;

- загальна дисперсія;

,(5.20)

де - емпіричне значення ;

- теоретичне значення ;

- середнє значення ;

,(5.21)

. (5.22)

Виходячи з даних міркувань:

(5.23)

Таблиця 5.3 - Таблиця аналізу дисперсій

Таблиця 5.4 - Таблиця аналізу дисперсій стосовно даних задачі

, (5.24)

.(5.25)

Таким чином:

, (5.26)

де - число ступенів свободи відповідно чисельника і знаменника.

. (5.27)

, , тобто розходження обґрунтованої та необґрунтованої складових дисперсії носить не випадковий характер і взаємозв'язок між рівнем споживання та рівнем доходу тісний.

5.3 Оцінка лінійного коефіцієнту кореляції

Оцінку лінійного коефіцієнта кореляції r виконаємо за такою формулою [3]:

, (5.28)

.(5.29)

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

5.4 Побудова довірчих інтервалів для , та

Побудова довірчого інтервалу для кутового коефіцієнту кореляції виконаємо за такою формулою [3]:

, (5.30)

де - деяка похибка при оцінці ;

- довірчий коефіцієнт при рівні імовірності та ступенях свободи. Знаходиться за таблицями -розподілу Ст'юдента.

Приймається якісна гіпотеза, відповідно до якої .

Формула для розрахунку має вигляд [3]:

, (5.31)

. (5.32)

; (5.33)

; ;(5.34)

. (5.35)

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

Побудову довірчого інтервалу для коефіцієнта виконаємо за такою формулою [3]:

, (5.36)

де - деяка похибка при оцінюванні ;

, (5.37)

. (5.38)

; ;(5.39)

(5.40)

До інтервалу входять як від'ємні, так і додатні значення, отже при 95% імовірності похибка при оцінюванні не істотно відмінна від нуля.

Побудову довірчого інтервалу для лінійного коефіцієнту кореляції виконаємо за такою формулою [3]:

, (5.41)

де - деяка похибка при оцінці ;

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

(5.42)

Розподіл приблизно співпадає з нормальним розподілом.

Тоді за таблицею - перетворення Фішера .

Знаходимо

, (5.43)

. (5.44)

Визначаємо при 95% рівні імовірності довірчі інтервали для :

; (5.45)

; (5.46)

. (5.47)

Скориставшись знову таблицями -перетворення Фішера, знайдемо тепер граничні значення для :

(5.48)

(5.49)

Отже

. (5.50)

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

5.5 Побудова знайденої лінії регресії на одному графіку з вихідними даними

В кінці рішення задачі побудуємо на одному графіку вихідні дані та лінію регресії (рис.5.1):

Рисунок 5.1 - Вихідні дані та лінія регресії

Висновок

Побудована споживча функція має вигляд: . Розходження обґрунтованої та необґрунтованої складових дисперсії носить не випадковий характер і взаємозв'язок між рівнем споживання та рівнем доходу тісний. Високий лінійний коефіцієнт кореляції свідчить про тісний взаємозв'язок між роздрібним товарообігом та рівнем доходу. Знайдений довірчий інтервал не має значень 0 та 1, тому результати регресії відповідають якісній гіпотезі, згідно до якої , тому робимо висновок про достатню точність оцінки . До довірчого інтервалу входять як від'ємні, так і додатні значення, отже при 95% імовірності похибка при оцінюванні не істотно відмінна від нуля. Оцінка лінійного коефіцієнту кореляції є досить точною, а значить, тіснота зв'язку між роздрібним товарообігом та рівнем доходу громадян є дуже високою.

ПЕРЕЛІК ПОСИЛАНЬ

1. Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003. - 452 с.

2. Курицкий Б.Я. Поиск оптимальных решений средствами Ехсеl 7.0. - СПб.: ВНV, 1997. - 384 с.

3. Наконечний С.І., Терещенко Т. О., Романюк Т. П. Економетрія: Підручник. - К.:КНЕУ, 1997. - 352с.

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