Реферати, курсові, дисертації, дипломи

[ Практикум за рішенням лінійних задач математичного програмування ]

<div style="font-size:16px;text-align:justify;">
	 ПРАКТИКУМ ЗГІДНО РІШЕННЯ ЛІНІЙНИХ ЗАВДАНЬ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ Введення Математичне <a href="Програмування" title="Програмування">програмування</a> - це розділ математики, який вивчає теорію та методи пошуку кращих варіантів <a href="Планування" title="Планування">планування</a> господарської діяльності людини як на одному певному підприємстві, так і в деякій галузі або в окремому регіоні, або в цілому державі. Кращі варіанти - це ті, при яких досягається максимальна <a href="Продуктивність" title="Продуктивність">продуктивність</a> праці, мінімум собівартості, максимальний <a href="Прибуток" title="Прибуток">прибуток</a>, мінімум використання <a href="Ресурси" title="Ресурси">ресурсів</a> і т.д. З точки зору математики - це клас оптимізаційних завдань. Основним інструментом при їх вирішенні є <a href="Математичне_моделювання" title="Математичне моделювання">математичне моделювання</a>. Математична модель - це формальний <a href="Опис" title="Опис">опис</a> досліджуваного явища і "переклад" всіх існуючих відомостей про нього на мову математики у вигляді рівнянь, тотожностей, <a href="Нерівності" title="Нерівності">нерівностей</a>. Якщо всі ці співвідношення лінійні, то вся завдання називається задачею лінійного <a href="Програмування" title="Програмування">програмування </a>(ЗЛП). Критерієм ефективності цієї моделі є деяка <a href="функція" title="функція">функція</a>, яку називають цільовою. Постановка задачі лінійного програмування та форми її записи Сформулюємо загальну задачу лінійного програмування. Нехай дана система m лінійних рівнянь і нерівностей з n змінними (система обмежень): <IMG SRC=dopc70468.zip NAME=graphics1 ALIGN=BOTTOM WIDTH=204 HEIGHT=148 BORDER=0> (1) і лінійна функція <IMG SRC=dopc70469.zip NAME=graphics2 ALIGN=BOTTOM WIDTH=136 HEIGHT=20 BORDER=0> . (2) Необхідно знайти таке рішення <IMG SRC=dopc70470.zip NAME=graphics3 ALIGN=BOTTOM WIDTH=96 HEIGHT=20 BORDER=0> системи (1), при якому лінійна функція <IMG SRC=dopc70471.zip NAME=graphics4 ALIGN=BOTTOM WIDTH=15 HEIGHT=15 BORDER=0> приймає максимальне (мінімальне) значення. У загальному випадку ЗЛП може <a href="Мати" title="Мати">мати</a> нескінченну безліч рішень. Часто рішення <IMG SRC=dopc70470.zip NAME=graphics5 ALIGN=BOTTOM WIDTH=96 HEIGHT=20 BORDER=0> , Що задовольняє обмеженням (1), називають планом. Якщо всі компоненти <IMG SRC=dopc70473.zip NAME=graphics6 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> (3) для <IMG SRC=dopc70474.zip NAME=graphics7 ALIGN=BOTTOM WIDTH=41 HEIGHT=24 BORDER=0> , То <IMG SRC=dopc70470.zip NAME=graphics8 ALIGN=BOTTOM WIDTH=96 HEIGHT=20 BORDER=0> називають допустимим рішенням. Оптимальним рішенням або оптимальним планом <a href="Завдання_лінійного_програмування" title="Завдання лінійного програмування">завдання лінійного програмування</a> називається таке її рішення <IMG SRC=dopc70476.zip NAME=graphics9 ALIGN=BOTTOM WIDTH=109 HEIGHT=23 BORDER=0> , Яке задовольняє всім обмеженням системи (1), умові (3) і при цьому дає максимум (мінімум) цільової <a href="Функції" title="Функції">функції</a> (2). <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=192><COL WIDTH=193><COL WIDTH=192><TR VALIGN=TOP><TD WIDTH=192> Канонічна </TD><TD WIDTH=193> Стандартна </TD><TD WIDTH=192> Загальна </TD></TR><TR><TD COLSPAN=3 WIDTH=604 VALIGN=TOP> 1) Обмеження </TD></TR><TR VALIGN=TOP><TD WIDTH=192> Рівняння <IMG SRC=dopc70477.zip NAME=graphics10 ALIGN=BOTTOM WIDTH=68 HEIGHT=43 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics11 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> </TD><TD WIDTH=193> Нерівності <IMG SRC=dopc70479.zip NAME=graphics12 ALIGN=BOTTOM WIDTH=76 HEIGHT=43 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics13 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> </TD><TD WIDTH=192> Рівняння і нерівності <IMG SRC=dopc70481.zip NAME=graphics14 ALIGN=BOTTOM WIDTH=76 HEIGHT=63 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics15 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> </TD></TR><TR><TD COLSPAN=3 WIDTH=604 VALIGN=TOP> 2) Умови неотрицательности </TD></TR><TR VALIGN=TOP><TD WIDTH=192> Всі змінні <IMG SRC=dopc70473.zip NAME=graphics16 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70474.zip NAME=graphics17 ALIGN=BOTTOM WIDTH=41 HEIGHT=24 BORDER=0> </TD><TD WIDTH=193> Всі змінні <IMG SRC=dopc70473.zip NAME=graphics18 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70474.zip NAME=graphics19 ALIGN=BOTTOM WIDTH=41 HEIGHT=24 BORDER=0> </TD><TD WIDTH=192> Частина змінних <IMG SRC=dopc70473.zip NAME=graphics20 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70488.zip NAME=graphics21 ALIGN=BOTTOM WIDTH=40 HEIGHT=24 BORDER=0> , <IMG SRC=dopc70489.zip NAME=graphics22 ALIGN=BOTTOM WIDTH=31 HEIGHT=13 BORDER=0> </TD></TR><TR><TD COLSPAN=3 WIDTH=604 VALIGN=TOP> 3) Цільова функція </TD></TR><TR><TD COLSPAN=3 WIDTH=604 VALIGN=TOP> <IMG SRC=dopc70490.zip NAME=graphics23 ALIGN=BOTTOM WIDTH=67 HEIGHT=43 BORDER=0> (Max або min) </TD></TR></TABLE></CENTER> Тут: <IMG SRC=dopc70491.zip NAME=graphics24 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> - <a href="Змінні" title="Змінні">Змінні</a> завдання; <IMG SRC=dopc70492.zip NAME=graphics25 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> - Коефіцієнти при змінних в цільовій функції; <IMG SRC=dopc70493.zip NAME=graphics26 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> - Коефіцієнти при змінних в основних обмеженнях задачі; <IMG SRC=dopc70494.zip NAME=graphics27 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> - Праві частини обмежень. Приклад. Скласти економіко-математичну модель задачі: Для випуску виробів двох типів А і В на заводі використовують сировину чотирьох видів (I, II, III, IV). Для виготовлення виробу А необхідно: 2 од. сировини першого виду, 1 од. другого виду, 2 од. третього виду та 1 од. четвертого виду. Для виготовлення виробу В потрібно: 3 од. сировини першого виду, 1 од. другого виду, 1 од. третього виду. Запаси сировини становлять: I вигляд а - 21 од., II виду - 8 од., III виду - 12 од., IV виду - 5 од. Випуск одного виробу типу А приносить 3 УДЕ прибутку, а одного виробу типу В - 2 УДЕ. Скласти <a href="План_виробництва" title="План виробництва">план виробництва</a>, що забезпечує найбільший <a href="Прибуток" title="Прибуток">прибуток</a>. Рішення. Досить часто при складанні <a href="Математика" title="Математика">математичної</a> моделі економічної задачі буває зручно дані умови представити у вигляді <a href="Таблиці" title="Таблиці">таблиці</a>: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=140><COL WIDTH=141><COL WIDTH=141><COL WIDTH=140><TR VALIGN=TOP><TD WIDTH=140 HEIGHT=5> Сировина </TD><TD COLSPAN=2 WIDTH=296> Кількість сировини на од. продукції, од. </TD><TD WIDTH=140> Запас сировини, од. </TD></TR><TR VALIGN=TOP><TD WIDTH=140 HEIGHT=2> </TD><TD WIDTH=141> А </TD><TD WIDTH=141> У </TD><TD WIDTH=140> </TD></TR><TR VALIGN=TOP><TD WIDTH=140> I </TD><TD WIDTH=141> 2 </TD><TD WIDTH=141> 3 </TD><TD WIDTH=140> 21 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> II </TD><TD WIDTH=141> 1 </TD><TD WIDTH=141> 1 </TD><TD WIDTH=140> 8 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> III </TD><TD WIDTH=141> 2 </TD><TD WIDTH=141> 1 </TD><TD WIDTH=140> 12 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> IV </TD><TD WIDTH=141> 1 </TD><TD WIDTH=141> - </TD><TD WIDTH=140> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> Прибуток від од. продукції, УДЕ </TD><TD WIDTH=141> 3 </TD><TD WIDTH=141> 2 </TD><TD WIDTH=140> </TD></TR></TABLE></CENTER> Нехай <IMG SRC=dopc70495.zip NAME=graphics28 ALIGN=BOTTOM WIDTH=32 HEIGHT=20 BORDER=0> - Кількість виробів типу А і В <a href="Відповідь" title="Відповідь">відповідно</a>, плановане до випуску ( <IMG SRC=dopc70496.zip NAME=graphics29 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70497.zip NAME=graphics30 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> ). </COL></COL></COL></COL></COL></COL></COL> Тоді прибуток складе: <IMG SRC=dopc70498.zip NAME=graphics31 ALIGN=BOTTOM WIDTH=52 HEIGHT=20 BORDER=0> , Т. к. план виробництва повинен забезпечувати найбільший прибуток, то цільова <a href="функція" title="функція">функція</a> задачі: <IMG SRC=dopc70499.zip NAME=graphics32 ALIGN=BOTTOM WIDTH=116 HEIGHT=20 BORDER=0> . Складемо систему обмежень, використовуючи задану обмеженість сировини. При запланованих обсягах виробництва витрачається сировини I види: <IMG SRC=dopc70500.zip NAME=graphics33 ALIGN=BOTTOM WIDTH=52 HEIGHT=20 BORDER=0> (Од.), що не повинно перевищувати запас 21 од. Т.ч. отримаємо нерівність: <IMG SRC=dopc70501.zip NAME=graphics34 ALIGN=BOTTOM WIDTH=80 HEIGHT=20 BORDER=0> . Складаючи <a href="Нерівності" title="Нерівності">нерівності</a> по кожному виду сировини, отримаємо систему: <IMG SRC=dopc70502.zip NAME=graphics35 ALIGN=BOTTOM WIDTH=87 HEIGHT=84 BORDER=0> Отримуємо <a href="Математика" title="Математика">математичну</a> модель задачі лінійного програмування: <IMG SRC=dopc70503.zip NAME=graphics36 ALIGN=BOTTOM WIDTH=116 HEIGHT=124 BORDER=0> Приклад. Скласти математичну модель задачі: На чотирьох верстатах (I, II, III, IV) обробляються два види деталей (А і В). Кожна деталь проходить обробку на всіх верстатах. Відомі час обробки деталей на кожному <a href="Верста" title="Верста">верстаті</a>, час <a href="Роботи" title="Роботи">роботи</a> верстатів протягом одного циклу виробництва і прибуток, отриманий від випуску однієї деталі. Дані наведені в таблиці: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=140><COL WIDTH=141><COL WIDTH=141><COL WIDTH=140><TR VALIGN=TOP><TD WIDTH=140 HEIGHT=5> Верстати </TD><TD COLSPAN=2 WIDTH=296> Час обробки деталі, ч. </TD><TD WIDTH=140> Час роботи верстата (Цикл пр-ва), ч. </TD></TR><TR VALIGN=TOP><TD WIDTH=140 HEIGHT=2> </TD><TD WIDTH=141> А </TD><TD WIDTH=141> У </TD><TD WIDTH=140> </TD></TR><TR VALIGN=TOP><TD WIDTH=140> I </TD><TD WIDTH=141> 1 </TD><TD WIDTH=141> 2 </TD><TD WIDTH=140> 16 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> II </TD><TD WIDTH=141> 2 </TD><TD WIDTH=141> 3 </TD><TD WIDTH=140> 26 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> III </TD><TD WIDTH=141> 1 </TD><TD WIDTH=141> 1 </TD><TD WIDTH=140> 10 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> IV </TD><TD WIDTH=141> 3 </TD><TD WIDTH=141> 1 </TD><TD WIDTH=140> 24 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> Прибуток від 1 деталі, УДЕ </TD><TD WIDTH=141> 4 </TD><TD WIDTH=141> 1 </TD><TD WIDTH=140> </TD></TR></TABLE></CENTER> Скласти план виробництва, що забезпечує найбільший прибуток за умови, що кількість деталей виду В не повинно бути менше кількості деталей види А. Рішення. Нехай <IMG SRC=dopc70495.zip NAME=graphics37 ALIGN=BOTTOM WIDTH=32 HEIGHT=20 BORDER=0> - Кількість деталей виду А і В <a href="Відповідь" title="Відповідь">відповідно</a>, плановане до випуску ( <IMG SRC=dopc70496.zip NAME=graphics38 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70497.zip NAME=graphics39 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> ). Завдання аналогічна попередньої, але при складанні моделі не слід випускати з поля зору фразу: кількість деталей виду В не повинно бути менше кількості деталей виду А, що <a href="Математика" title="Математика">математично</a> представимо у вигляді нерівності: <IMG SRC=dopc70507.zip NAME=graphics40 ALIGN=BOTTOM WIDTH=39 HEIGHT=20 BORDER=0> . Тоді <a href="Математика" title="Математика">математична</a> модель задачі лінійного програмування має вигляд: <IMG SRC=dopc70508.zip NAME=graphics41 ALIGN=BOTTOM WIDTH=111 HEIGHT=145 BORDER=0> Будь-яка ЗЛП може бути зведена до канонічної, <a href="Стандарт" title="Стандарт">стандартної</a> або загальному завданню. Приведення завдань до канонічного вигляду Нехай маємо задачу загального вигляду, яку потрібно привести до канонічного виду, тобто з обмежень-нерівностей зробити обмеження-рівності. Для цього в кожне обмеження вводиться додаткова неотрицательная балансова мінлива зі знаком «+», якщо <a href="Знак" title="Знак">знак</a> нерівності « <IMG SRC=dopc70509.zip NAME=graphics42 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> », І зі знаком« - », якщо знак нерівності« <IMG SRC=dopc70510.zip NAME=graphics43 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> ». У цільову функцію ці <a href="Змінні" title="Змінні">змінні</a> входять з нульовими коефіцієнтами, тобто значення цільової функції не змінюється. Примітка: 1) У канонічній формі рівності прийнято записувати так, щоб праві частини обмежень були невід'ємними. Якщо будь-яка <IMG SRC=dopc70494.zip NAME=graphics44 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> негативне, то помноживши i-е обмеження на (-1), отримаємо в правій частині позитивне число. При цьому знак нерівності потрібно змінити на протилежний. 2) Якщо обмеження містить знак «=», то додаткову змінну вводити не потрібно. Приклад. Записати задачу лінійного програмування в канонічному вигляді. <IMG SRC=dopc70512.zip NAME=graphics45 ALIGN=BOTTOM WIDTH=92 HEIGHT=20 BORDER=0> max (min) <IMG SRC=dopc70513.zip NAME=graphics46 ALIGN=BOTTOM WIDTH=115 HEIGHT=63 BORDER=0> <IMG SRC=dopc70514.zip NAME=graphics47 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70515.zip NAME=graphics48 ALIGN=BOTTOM WIDTH=39 HEIGHT=24 BORDER=0> Рішення. Друге обмеження системи містить в правій частині негативне число -2. Помножимо друге обмеження на (-1), при цьому знак нерівності <IMG SRC=dopc70510.zip NAME=graphics49 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> зміниться на протилежний <IMG SRC=dopc70509.zip NAME=graphics50 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> . Завдання прийме вигляд: <IMG SRC=dopc70512.zip NAME=graphics51 ALIGN=BOTTOM WIDTH=92 HEIGHT=20 BORDER=0> max (min) <IMG SRC=dopc70519.zip NAME=graphics52 ALIGN=BOTTOM WIDTH=109 HEIGHT=63 BORDER=0> <IMG SRC=dopc70514.zip NAME=graphics53 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70515.zip NAME=graphics54 ALIGN=BOTTOM WIDTH=39 HEIGHT=24 BORDER=0> У перше і в друге обмеження додамо по додаткової змінної <IMG SRC=dopc70522.zip NAME=graphics55 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70523.zip NAME=graphics56 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> відповідно, а з третього віднімемо додаткову зміну <IMG SRC=dopc70524.zip NAME=graphics57 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> . Маємо наступний канонічний вигляд завдання: <IMG SRC=dopc70512.zip NAME=graphics58 ALIGN=BOTTOM WIDTH=92 HEIGHT=20 BORDER=0> max (min) <IMG SRC=dopc70526.zip NAME=graphics59 ALIGN=BOTTOM WIDTH=133 HEIGHT=63 BORDER=0> <IMG SRC=dopc70514.zip NAME=graphics60 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70528.zip NAME=graphics61 ALIGN=BOTTOM WIDTH=39 HEIGHT=24 BORDER=0> Завдання для самостійної роботи. Скласти економіко-математичні моделі наступних завдань: <OL><LI> Для виготовлення двох видів продукції P 1 і Р 2 використовують чотири види ресурсів S 1, S 2, S 3 і S 4. Запаси ресурсів, число одиниць ресурсів, що витрачаються на виготовлення одиниці продукції, наведені в таблиці: <LI></OL><CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=140><COL WIDTH=141><COL WIDTH=141><COL WIDTH=140><TR VALIGN=TOP><TD WIDTH=140> Вид ресурсу </TD><TD WIDTH=141> Запас ресурсу </TD><TD COLSPAN=2 WIDTH=295> Число од. ресурсів, витрачених на виготовлення од. продукції </TD></TR><TR VALIGN=TOP><TD WIDTH=140 HEIGHT=3> </TD><TD WIDTH=141> </TD><TD WIDTH=141> Р1 </TD><TD WIDTH=140> Р2 </COL></COL></COL></COL></LI></LI></TD></TR></COL></COL></COL></COL></TABLE></CENTER><CENTER><TABLE><TR><TD></TD></TR><TR VALIGN=TOP><TD WIDTH=140> S1 </TD><TD WIDTH=141> 18 </TD><TD WIDTH=141> 1 </TD><TD WIDTH=140> 3 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> S2 </TD><TD WIDTH=141> 16 </TD><TD WIDTH=141> 2 </TD><TD WIDTH=140> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> S3 </TD><TD WIDTH=141> 5 </TD><TD WIDTH=141> - </TD><TD WIDTH=140> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=140> S4 </TD><TD WIDTH=141> 21 </TD><TD WIDTH=141> 3 </TD><TD WIDTH=140> - </TD></TR></TABLE></CENTER> Прибуток, що отримується від одиниці продукції Р 1 і Р 2, - відповідно 2 грн. і 3 грн. <OL START=3><LI> На придбання обладнання для нового виробничого ділянки загальною площею 375 м 2 підприємство володіє необхідною кількістю грошових коштів. Підприємство може замовити обладнання двох видів: машини першого типу вартістю 10000 грн., Що вимагають продуктивну площа 6 м 2 (з урахуванням проходів), що виробляють 4000 одиниць продукції за зміну, і машини другого типу вартістю 20000 грн., Що займають 10 м 2 площі, що виробляють 5000 одиниць продукції за зміну. Загальна продуктивність даного виробничого ділянки повинна бути не менше 221000 одиниць продукції за зміну. Побудувати модель задачі за умови, що оптимальним для підприємства варіантом придбання обладнання вважається той, який забезпечує найменші загальні <a href="Витрати" title="Витрати">витрати</a>. <LI> Фермер планує виробити не менше 120 тонн пшениці, 70 тонн кукурудзи і 15 тонн гречки. Для цього можна використовувати два <a href="Масиви" title="Масиви">масиви</a> сільськогосподарських угідь в 1000 і 800 га. У таблиці наведені врожайність кожної культури на різних ділянках (верхній показник) і <a href="Витрати" title="Витрати">витрати</a> на 1 га сільськогосподарських угідь при виробництві різних культур (нижній показник). Потрібно скласти <a href="Такий" title="Такий">такий</a> план засіву, щоб валовий збір зерна задовольняв планового завдання, а вартість витрат була найменшою. </OL><CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=98><COL WIDTH=103><COL WIDTH=119><COL WIDTH=119><COL WIDTH=109><TR VALIGN=TOP><TD WIDTH=98> Поле </TD><TD WIDTH=103> Розмір поля </TD><TD COLSPAN=3 WIDTH=374> Культури </TD></TR><TR VALIGN=TOP><TD WIDTH=98 HEIGHT=2> </TD><TD WIDTH=103> </TD><TD WIDTH=119> пшениця </TD><TD WIDTH=119> кукурудза </TD><TD WIDTH=109> гречка </TD></TR><TR VALIGN=TOP><TD WIDTH=98> I </TD><TD WIDTH=103> 1000 </TD><TD WIDTH=119> 10 7 </TD><TD WIDTH=119> 20 10 </TD><TD WIDTH=109> 6 15 </TD></TR><TR VALIGN=TOP><TD WIDTH=98> II </TD><TD WIDTH=103> 800 </TD><TD WIDTH=119> 12 8 </TD><TD WIDTH=119> 24 12 </TD><TD WIDTH=109> 5 20 </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=215> План по культурах </TD><TD WIDTH=119> 120 </TD><TD WIDTH=119> 70 </TD><TD WIDTH=109> 15 </TD></TR></TABLE></CENTER><OL START=5><LI> Фірма має можливість рекламувати свою продукцію, використовуючи для цього <a href="Телебачення" title="Телебачення">телебачення</a>, радіо і газети. Витрати на рекламу в <a href="Бюджет" title="Бюджет">бюджеті</a> <a href="Фірми" title="Фірми">фірми</a> обмежені сумою 8000 грн. в місяць. Досвід минулих років показав, що 1 грн., Витрачена на телерекламу, дає фірмі прибуток у розмірі 10 грн., А витрачена на рекламу по радіо і в <a href="Газета" title="Газета">газетах</a> - відповідно 4 і 8 грн. </OL> Фірма має намір <a href="Витрати" title="Витрати">витратити</a> на теле-і радіорекламу не більше 70% рекламного <a href="Бюджет" title="Бюджет">бюджету</a>, а витрати на газетну рекламу не повинні більше ніж удвічі перевищувати витрати на радіорекламу. Визначити такий варіант розподілу рекламного бюджету за різними напрямами реклами, який дає фірмі найбільший прибуток від реклами своєї продукції. <OL START=6><LI> Продукція фабрики випускається у вигляді паперових рулонів стандартної ширини - 2 м. За спеціальним прохання споживачів фабрика поставляє також рулони інших розмірів, розрізаючи <a href="Стандарт" title="Стандарт">стандартні</a> рулони. Типові заявки на рулони нестандартних розмірів наведені в таблиці: </OL><CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=192><COL WIDTH=193><COL WIDTH=192><TR VALIGN=TOP><TD WIDTH=192> Заявка </TD><TD WIDTH=193> Потрібна ширина рулону, м </TD><TD WIDTH=192> Потрібне кол-во рулонів </TD></TR><TR VALIGN=TOP><TD WIDTH=192> 1 </TD><TD WIDTH=193> 0,8 </TD><TD WIDTH=192> 150 </TD></TR><TR VALIGN=TOP><TD WIDTH=192> 2 </TD><TD WIDTH=193> 1,0 </TD><TD WIDTH=192> 200 </TD></TR><TR VALIGN=TOP><TD WIDTH=192> 3 </TD><TD WIDTH=193> 1,2 </TD><TD WIDTH=192> 300 </TD></TR></TABLE></CENTER> Визначити оптимальний варіант розкрою <a href="Стандарт" title="Стандарт">стандартних</a> рулонів, при якому всі вступники спеціальні заявки будуть виконані при мінімальних <a href="Витрати" title="Витрати">витратах</a> паперу. Графічний метод розв'язання задач лінійного програмування 1. Область рішень лінійних нерівностей. Нехай задано лінійне нерівність з двома змінними <IMG SRC=dopc70529.zip NAME=graphics62 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70530.zip NAME=graphics63 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> <IMG SRC=dopc70531.zip NAME=graphics64 ALIGN=BOTTOM WIDTH=11 HEIGHT=20 BORDER=0><IMG SRC=dopc70532.zip NAME=graphics65 ALIGN=BOTTOM WIDTH=101 HEIGHT=20 BORDER=0> (1) Якщо величини <IMG SRC=dopc70529.zip NAME=graphics66 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70530.zip NAME=graphics67 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> розглядати як координати точки площини, то сукупність точок площини, координати яких задовольняють <a href="Нерівності" title="Нерівності">нерівності </a>(1), називається областю рішень даного нерівності. Отже, областю рішень нерівності (1) є полуплоскость з граничною прямою лінією <IMG SRC=dopc70535.zip NAME=graphics68 ALIGN=BOTTOM WIDTH=100 HEIGHT=20 BORDER=0> . Приклад 1. Знайти полуплоскость, яка визначається нерівністю <IMG SRC=dopc70536.zip NAME=graphics69 ALIGN=BOTTOM WIDTH=96 HEIGHT=20 BORDER=0> . Рішення. Будуємо пряму <IMG SRC=dopc70537.zip NAME=graphics70 ALIGN=BOTTOM WIDTH=97 HEIGHT=20 BORDER=0> по двох точках, наприклад, по точках перетину з осями координат (0; 4) і (6; 0). Ця лінія ділить площину на дві частини, тобто на дві півплощини. Беремо будь-яку точку площини, що не лежить на побудованій прямій. Якщо координати точки задовольняють заданому нерівності, то областю рішень є та полуплоскость, в якій знаходиться ця точка. Якщо ж отримуємо невірне числове нерівність, то областю рішень є та полуплоскость, якій ця точка не належить. Зазвичай для контролю беруть точку (0; 0). Підставимо <IMG SRC=dopc70538.zip NAME=graphics71 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70539.zip NAME=graphics72 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> в заданий нерівність. Отримаємо <IMG SRC=dopc70540.zip NAME=graphics73 ALIGN=BOTTOM WIDTH=45 HEIGHT=16 BORDER=0> . Отже, полуплоскость «до нуля» є областю рішень даного нерівності (заштрихована частина рис. 1). Приклад 2. Знайти полуплоскость, яка визначається нерівністю <IMG SRC=dopc70541.zip NAME=graphics74 ALIGN=BOTTOM WIDTH=65 HEIGHT=20 BORDER=0> . Рішення. Будуємо пряму <IMG SRC=dopc70542.zip NAME=graphics75 ALIGN=BOTTOM WIDTH=65 HEIGHT=20 BORDER=0> , Наприклад, по точках (0; 0) і (1, 3). Оскільки пряма проходить через початок координат, точку (0; 0), то не можна <a href="Брати" title="Брати">брати</a> її для контролю. Візьмемо, наприклад, точку (- 2; 0) і <a href="Підстави" title="Підстави">підставимо</a> її координати в заданий нерівність. Отримаємо <IMG SRC=dopc70543.zip NAME=graphics76 ALIGN=BOTTOM WIDTH=39 HEIGHT=16 BORDER=0> . Це невірно. Значить, областю рішень даного нерівності буде та полуплоскость, якої не належить <a href="Контроль" title="Контроль">контрольний</a> пункт (заштрихована частина рис. 2). 2. Область рішень системи лінійних нерівностей. </COL></COL></COL></LI></LI></COL></COL></COL></COL></COL></LI></LI> Приклад. Знайти область рішень системи нерівностей: <IMG SRC=dopc70544.zip NAME=graphics77 ALIGN=BOTTOM WIDTH=103 HEIGHT=44 BORDER=0> Рішення. Знаходимо область рішень I-го нерівності (рис. 1) і II-го нерівності (рис. 2). Всі крапки частини площині, де штрихування наклалася, будуть задовольняти і першому і другому нерівності. Таким чином, отримана область рішень заданої системи <a href="Нерівності" title="Нерівності">нерівностей </a>(рис. 3). Якщо до заданій системі нерівностей додати умови <IMG SRC=dopc70545.zip NAME=graphics78 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70546.zip NAME=graphics79 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> , То область рішень системи нерівностей <IMG SRC=dopc70547.zip NAME=graphics80 ALIGN=BOTTOM WIDTH=103 HEIGHT=63 BORDER=0> буде знаходитися тільки в I координатної чверті (рис. 4). Принцип знаходження рішення системи лінійних нерівностей не залежить від кількості нерівностей, що входять в систему. Примітка: Область допустимих рішень (ОДР) якщо існує, то є замкнутий або незамкнений опуклий багатокутник. 3. Алгоритм графічного методу розв'язання ЗЛП Якщо завдання лінійного програмування містить тільки дві змінні, то її можна вирішити графічним методом, виконуючи такі операції: <OL><LI> Будуємо всі півплощини, <a href="Відповідь" title="Відповідь">відповідні</a> обмеженням системи. <LI> Знаходимо область допустимих рішень (ОДР), як безліч точок, в якому перетинаються всі побудовані півплощини. <LI> Будуємо вектор <IMG SRC=dopc70548.zip NAME=graphics81 ALIGN=BOTTOM WIDTH=51 HEIGHT=23 BORDER=0> , Що виходить з початку координат, де <IMG SRC=dopc70549.zip NAME=graphics82 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70550.zip NAME=graphics83 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> - Це коефіцієнти при невідомих у цільовій функції <IMG SRC=dopc70551.zip NAME=graphics84 ALIGN=BOTTOM WIDTH=83 HEIGHT=20 BORDER=0> . Цей вектор вказує напрям зростання цільової функції. <LI> Перпендикулярно вектору <IMG SRC=dopc70552.zip NAME=graphics85 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> проводимо так звану лінію рівня <IMG SRC=dopc70553.zip NAME=graphics86 ALIGN=BOTTOM WIDTH=33 HEIGHT=16 BORDER=0> (Тобто пряму <IMG SRC=dopc70554.zip NAME=graphics87 ALIGN=BOTTOM WIDTH=79 HEIGHT=20 BORDER=0> , Що проходить через початок координат). <LI> Переміщаємо лінію рівня <IMG SRC=dopc70553.zip NAME=graphics88 ALIGN=BOTTOM WIDTH=33 HEIGHT=16 BORDER=0> паралельно самій собі в напрямку вектора <IMG SRC=dopc70552.zip NAME=graphics89 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> (Якщо завдання на максимум (max)) або в протилежному напрямку (якщо завдання на мінімум (min)) до тих пір, поки лінія рівня має хоча б одну спільну точку з ОДР. <LI> Знаходимо координати <IMG SRC=dopc70557.zip NAME=graphics90 ALIGN=BOTTOM WIDTH=40 HEIGHT=20 BORDER=0> цієї загальної крайньої точки, вирішуючи систему рівнянь прямих, на перетині яких вона знаходиться. <LI> Підставляємо ці координати в цільову функцію і знаходимо її max (Або min). </OL> Приклад. Вирішити задачу лінійного програмування графічним методом <IMG SRC=dopc70558.zip NAME=graphics91 ALIGN=BOTTOM WIDTH=97 HEIGHT=20 BORDER=0> max <IMG SRC=dopc70559.zip NAME=graphics92 ALIGN=BOTTOM WIDTH=87 HEIGHT=84 BORDER=0> Рішення. Третє і <a href="Четверо" title="Четверо">четверте</a> обмеження системи - подвійні нерівності, перетворимо їх до більш звичного для подібних завдань увазі <IMG SRC=dopc70560.zip NAME=graphics93 ALIGN=BOTTOM WIDTH=56 HEIGHT=20 BORDER=0> , Це <IMG SRC=dopc70561.zip NAME=graphics94 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70562.zip NAME=graphics95 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , Таким чином перше з отриманих нерівностей <IMG SRC=dopc70561.zip NAME=graphics96 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> (Або <IMG SRC=dopc70545.zip NAME=graphics97 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> ) Відноситься до умови неотрицательности, а друге <IMG SRC=dopc70562.zip NAME=graphics98 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> до системи обмежень. Аналогічно, <IMG SRC=dopc70566.zip NAME=graphics99 ALIGN=BOTTOM WIDTH=59 HEIGHT=20 BORDER=0> це <IMG SRC=dopc70567.zip NAME=graphics100 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70568.zip NAME=graphics101 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> . Т.ч. завдання набуде вигляду <IMG SRC=dopc70558.zip NAME=graphics102 ALIGN=BOTTOM WIDTH=97 HEIGHT=20 BORDER=0> max <IMG SRC=dopc70570.zip NAME=graphics103 ALIGN=BOTTOM WIDTH=87 HEIGHT=84 BORDER=0> <IMG SRC=dopc70514.zip NAME=graphics104 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70572.zip NAME=graphics105 ALIGN=BOTTOM WIDTH=40 HEIGHT=24 BORDER=0> Замінивши знаки нерівностей на знаки точних рівностей, побудуємо область допустимих рішень по рівняннях прямих: <IMG SRC=dopc70573.zip NAME=graphics106 ALIGN=BOTTOM WIDTH=80 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70574.zip NAME=graphics107 ALIGN=BOTTOM WIDTH=65 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70575.zip NAME=graphics108 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70576.zip NAME=graphics109 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> . Областю рішень нерівностей є п'ятикутник ABCDE. Побудуємо вектор <IMG SRC=dopc70577.zip NAME=graphics110 ALIGN=BOTTOM WIDTH=51 HEIGHT=23 BORDER=0> . Через початок координат <a href="Перпендикуляр" title="Перпендикуляр">перпендикулярно</a> вектору <IMG SRC=dopc70578.zip NAME=graphics111 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> проведемо лінію рівня <IMG SRC=dopc70579.zip NAME=graphics112 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> . І потім будемо переміщати її паралельно самій собі в напрямку вектора <IMG SRC=dopc70578.zip NAME=graphics113 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> до точки виходу з області допустимих рішень. Це буде точка С. Знайдемо координати цієї точки, розв'язавши систему, що складається з рівнянь першої та четвертої прямих: <IMG SRC=dopc70581.zip NAME=graphics114 ALIGN=BOTTOM WIDTH=87 HEIGHT=44 BORDER=0><IMG SRC=dopc70582.zip NAME=graphics115 ALIGN=BOTTOM WIDTH=19 HEIGHT=15 BORDER=0><IMG SRC=dopc70583.zip NAME=graphics116 ALIGN=BOTTOM WIDTH=88 HEIGHT=44 BORDER=0><IMG SRC=dopc70582.zip NAME=graphics117 ALIGN=BOTTOM WIDTH=19 HEIGHT=15 BORDER=0><IMG SRC=dopc70585.zip NAME=graphics118 ALIGN=BOTTOM WIDTH=47 HEIGHT=60 BORDER=0><IMG SRC=dopc70582.zip NAME=graphics119 ALIGN=BOTTOM WIDTH=19 HEIGHT=15 BORDER=0><IMG SRC=dopc70587.zip NAME=graphics120 ALIGN=BOTTOM WIDTH=48 HEIGHT=41 BORDER=0> . Підставимо координати точки С в цільову функцію і знайдемо її максимальне значення <IMG SRC=dopc70588.zip NAME=graphics121 ALIGN=BOTTOM WIDTH=199 HEIGHT=37 BORDER=0> Приклад. Побудувати лінії рівня <IMG SRC=dopc70589.zip NAME=graphics122 ALIGN=BOTTOM WIDTH=28 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70590.zip NAME=graphics123 ALIGN=BOTTOM WIDTH=27 HEIGHT=20 BORDER=0> для задачі лінійного програмування: <IMG SRC=dopc70591.zip NAME=graphics124 ALIGN=BOTTOM WIDTH=95 HEIGHT=20 BORDER=0> max (min) <IMG SRC=dopc70592.zip NAME=graphics125 ALIGN=BOTTOM WIDTH=84 HEIGHT=63 BORDER=0> Рішення. Область допустимих рішень - відкрита область (рис. 6). Лінія рівня <IMG SRC=dopc70590.zip NAME=graphics126 ALIGN=BOTTOM WIDTH=27 HEIGHT=20 BORDER=0> проходить через точку В. Функція Z має мінімум в цій точці. Лінію рівня <IMG SRC=dopc70589.zip NAME=graphics127 ALIGN=BOTTOM WIDTH=28 HEIGHT=20 BORDER=0> побудувати не можна, так як немає точки виходу з області допустимих рішень, це означає, що <IMG SRC=dopc70595.zip NAME=graphics128 ALIGN=BOTTOM WIDTH=52 HEIGHT=20 BORDER=0> . Завдання для самостійної роботи. <OL><LI> Знайти область рішень системи нерівностей: </OL> а) <IMG SRC=dopc70596.zip NAME=graphics129 ALIGN=BOTTOM WIDTH=83 HEIGHT=84 BORDER=0> б) <IMG SRC=dopc70597.zip NAME=graphics130 ALIGN=BOTTOM WIDTH=83 HEIGHT=103 BORDER=0> <OL START=2><LI> Вирішити графічно задачу лінійного програмування </OL> <IMG SRC=dopc70598.zip NAME=graphics131 ALIGN=BOTTOM WIDTH=92 HEIGHT=20 BORDER=0> min <IMG SRC=dopc70599.zip NAME=graphics132 ALIGN=BOTTOM WIDTH=83 HEIGHT=84 BORDER=0> <OL START=3><LI> Скласти економіко-математичну модель і вирішити графічно задачу лінійного програмування </OL> Фірма випускає вироби двох видів А і В. Вироби кожного виду обробляють на двох верстатах (I і II). Час обробки одного виробу кожного виду на верстатах, час роботи верстатів за робочу зміну,<a href="Прибуток" title="Прибуток"> прибуток</a> фірми від реалізації одного виробу виду А і виду В занесені в таблицю: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=179><COL WIDTH=98><COL WIDTH=98><COL WIDTH=186><TR VALIGN=TOP><TD WIDTH=179> Верстати </TD><TD COLSPAN=2 WIDTH=211> Час обробки одного виробу, хв. </TD><TD WIDTH=186> Час роботи <a href="Верста" title="Верста">верстата</a> за зміну, хв. </TD></TR></COL></COL></COL></COL></TABLE></CENTER></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></TD></TR><TR VALIGN=TOP><TD WIDTH=179> </TD><TD WIDTH=98> А </TD><TD WIDTH=98> У </TD><TD WIDTH=186> </TD></TR><TR VALIGN=TOP><TD WIDTH=179> I </TD><TD WIDTH=98> 10 </TD><TD WIDTH=98> 20 </TD><TD WIDTH=186> 1300 </TD></TR><TR VALIGN=TOP><TD WIDTH=179> II </TD><TD WIDTH=98> 4 </TD><TD WIDTH=98> 13 </TD><TD WIDTH=186> 720 </TD></TR><TR VALIGN=TOP><TD WIDTH=179> Прибуток від одного виробу, грн. </TD><TD WIDTH=98> 0,3 </TD><TD WIDTH=98> 0,9 </TD><TD WIDTH=186> </TD></TR></TABLE></CENTER> Вивчення ринку збуту показало, що щоденний попит на вироби виду В ніколи не перевищує попит на вироби виду А більше ніж на 40 одиниць, а попит на вироби виду А не перевищує 90 одиниць на день. Визначити план виробництва виробів, що забезпечує найбільший прибуток. Симплексний метод розв'язання задач лінійного програмування Симплексний метод - це метод послідовного поліпшення плану. Цим методом можна розв'язувати задачі лінійного програмування з будь-якою кількістю змінних і обмежень. Цей метод включає в себе три основні етапи: <OL><LI> Побудова початкового опорного плану. <LI> Правило переходу на краще (точніше, нехудшему) рішенням. <LI> Критерій перевірки знайденого рішення на оптимальність. </OL> При симплексному методі виконуються обчислювальні процедури (ітерації) одного і <a href="Того" title="Того">того</a> ж типу в певній <a href="Послідовності" title="Послідовності">послідовності</a> до тих пір, поки не буде отриманий оптимальний план завдання або стане ясно, що його не існує. 1) Побудова початкового опорного плану. Дану задачу лінійного програмування необхідно спочатку привести до канонічного виду, при цьому праві частини обмежень повинні бути невід'ємними. Ознакою можливості побудови початкового опорного плану служить наявність у кожному обмеження-рівність з неотрицательной правою частиною базисної змінної. Базисної називають планову змінну, яка входить тільки в одне рівняння (а в інші не входить), і при цьому має коефіцієнт, що дорівнює одиниці. Нехай задача лінійного програмування приведена до канонічного вигляду, і всі рівняння системи обмежень мають свою базисну змінну. Прирівнявши базисні змінні до <a href="Відповідь" title="Відповідь">відповідних</a> правим частинам обмежень, а інші змінні до нуля, отримаємо опорне або базисне рішення задачі. Приклад. Для даної задачі лінійного програмування знайти початковий опорний план (базисне рішення). <IMG SRC=dopc70600.zip NAME=graphics133 ALIGN=BOTTOM WIDTH=159 HEIGHT=20 BORDER=0> max <IMG SRC=dopc70601.zip NAME=graphics134 ALIGN=BOTTOM WIDTH=135 HEIGHT=89 BORDER=0> Рішення. Змінимо знаки другого і третього нерівностей на протилежні, помноживши кожне з них на -1. Система обмежень тепер буде такою: <IMG SRC=dopc70602.zip NAME=graphics135 ALIGN=BOTTOM WIDTH=137 HEIGHT=63 BORDER=0> У кожному обмеження зліва додамо позитивну змінну <IMG SRC=dopc70603.zip NAME=graphics136 ALIGN=BOTTOM WIDTH=48 HEIGHT=20 BORDER=0> ,<a href="Відповідь" title="Відповідь"> Відповідно</a> запишемо канонічний вигляд завдання: <IMG SRC=dopc70600.zip NAME=graphics137 ALIGN=BOTTOM WIDTH=159 HEIGHT=20 BORDER=0> max <IMG SRC=dopc70605.zip NAME=graphics138 ALIGN=BOTTOM WIDTH=163 HEIGHT=63 BORDER=0> <IMG SRC=dopc70606.zip NAME=graphics139 ALIGN=BOTTOM WIDTH=84 HEIGHT=24 BORDER=0> . Змінні <IMG SRC=dopc70603.zip NAME=graphics140 ALIGN=BOTTOM WIDTH=48 HEIGHT=20 BORDER=0> базисні. Прирівнюємо їх до правих частин обмежень: <IMG SRC=dopc70608.zip NAME=graphics141 ALIGN=BOTTOM WIDTH=125 HEIGHT=20 BORDER=0> Всі інші змінні - вільні, прирівнюємо їх до нуля: <IMG SRC=dopc70609.zip NAME=graphics142 ALIGN=BOTTOM WIDTH=113 HEIGHT=20 BORDER=0> Запишемо тепер початковий опорний план <IMG SRC=dopc70610.zip NAME=graphics143 ALIGN=BOTTOM WIDTH=176 HEIGHT=21 BORDER=0> (0, 0, 0, 0, 16: 4; 0). 2) Складання симплексних таблиць. Критерій оптимальності. Симплексний метод зручно застосовувати, використовуючи побудова симплексних таблиць. Перша симплексна таблиця, <a href="Відповідь" title="Відповідь">відповідна</a> початкового плану, має вигляд: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=82><COL WIDTH=63><COL WIDTH=59><COL WIDTH=62><COL WIDTH=63><COL WIDTH=59><COL WIDTH=63><COL WIDTH=55><TR VALIGN=TOP><TD WIDTH=82> Базис </TD><TD WIDTH=63> <IMG SRC=dopc70611.zip NAME=graphics144 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> </TD><TD WIDTH=59> У </TD><TD WIDTH=62> <IMG SRC=dopc70612.zip NAME=graphics145 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70550.zip NAME=graphics146 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> <IMG SRC=dopc70614.zip NAME=graphics147 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> <IMG SRC=dopc70615.zip NAME=graphics148 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=82> </TD><TD WIDTH=63> </TD><TD WIDTH=59> </TD><TD WIDTH=62> <IMG SRC=dopc70529.zip NAME=graphics149 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70530.zip NAME=graphics150 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> <IMG SRC=dopc70618.zip NAME=graphics151 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> </TD></TR><TR VALIGN=TOP><TD WIDTH=82 HEIGHT=17> <IMG SRC=dopc70619.zip NAME=graphics152 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70620.zip NAME=graphics153 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> </TD><TD WIDTH=59> <IMG SRC=dopc70621.zip NAME=graphics154 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> </TD><TD WIDTH=62> <IMG SRC=dopc70622.zip NAME=graphics155 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70623.zip NAME=graphics156 ALIGN=BOTTOM WIDTH=20 HEIGHT=20 BORDER=0> </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> <IMG SRC=dopc70624.zip NAME=graphics157 ALIGN=BOTTOM WIDTH=20 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> </TD></TR><TR VALIGN=TOP><TD WIDTH=82 HEIGHT=17> <IMG SRC=dopc70625.zip NAME=graphics158 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70626.zip NAME=graphics159 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> </TD><TD WIDTH=59> <IMG SRC=dopc70627.zip NAME=graphics160 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=62> <IMG SRC=dopc70628.zip NAME=graphics161 ALIGN=BOTTOM WIDTH=20 HEIGHT=20 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70629.zip NAME=graphics162 ALIGN=BOTTOM WIDTH=20 HEIGHT=20 BORDER=0> </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> <IMG SRC=dopc70630.zip NAME=graphics163 ALIGN=BOTTOM WIDTH=21 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> </TD></TR><TR VALIGN=TOP><TD WIDTH=82 HEIGHT=17> ... </TD><TD WIDTH=63> ... </TD><TD WIDTH=59> ... </TD><TD WIDTH=62> ... </TD><TD WIDTH=63> ... </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> ... </TD><TD WIDTH=55> </TD></TR><TR VALIGN=TOP><TD WIDTH=82 HEIGHT=17> <IMG SRC=dopc70631.zip NAME=graphics164 ALIGN=BOTTOM WIDTH=20 HEIGHT=23 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70632.zip NAME=graphics165 ALIGN=BOTTOM WIDTH=20 HEIGHT=23 BORDER=0> </COL></COL></COL></COL></COL></COL></COL></COL></LI></LI></LI></TD><TD WIDTH=59> <IMG SRC=dopc70633.zip NAME=graphics166 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=62> <IMG SRC=dopc70634.zip NAME=graphics167 ALIGN=BOTTOM WIDTH=21 HEIGHT=20 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70635.zip NAME=graphics168 ALIGN=BOTTOM WIDTH=23 HEIGHT=20 BORDER=0> </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> <IMG SRC=dopc70636.zip NAME=graphics169 ALIGN=BOTTOM WIDTH=23 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=159 HEIGHT=16> <IMG SRC=dopc70637.zip NAME=graphics170 ALIGN=BOTTOM WIDTH=69 HEIGHT=21 BORDER=0> </TD><TD WIDTH=59> <IMG SRC=dopc70638.zip NAME=graphics171 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=62> <IMG SRC=dopc70639.zip NAME=graphics172 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=63> <IMG SRC=dopc70640.zip NAME=graphics173 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=59> ... </TD><TD WIDTH=63> <IMG SRC=dopc70641.zip NAME=graphics174 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> </TD></TR></TABLE></CENTER> Тут прийняті наступні позначення. Стовпець «Базис» - це базисні змінні. Стовпець « <IMG SRC=dopc70642.zip NAME=graphics175 ALIGN=BOTTOM WIDTH=25 HEIGHT=24 BORDER=0> »- Це коефіцієнти при базисних змінних у цільовій функції. Стовпець «В» - праві частини обмежень; <IMG SRC=dopc70643.zip NAME=graphics176 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> - Коефіцієнти при змінних в обмеженнях; <IMG SRC=dopc70644.zip NAME=graphics177 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> - Коефіцієнти при змінних в цільовій функції. Останній рядок у <a href="Таблиці" title="Таблиці">таблиці </a>( <IMG SRC=dopc70637.zip NAME=graphics178 ALIGN=BOTTOM WIDTH=69 HEIGHT=21 BORDER=0> ) - Це перевірочна або оціночна рядок. <IMG SRC=dopc70646.zip NAME=graphics179 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> - Значення цільової функції, <a href="Відповідь" title="Відповідь">відповідне</a> побудованому початкового плану. Його знаходять так: кожен елемент стовпця <IMG SRC=dopc70611.zip NAME=graphics180 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> множать на <a href="Відповідь" title="Відповідь">відповідний</a> елемент стовпця В і <a href="Твори" title="Твори">твори</a> складають, тобто <IMG SRC=dopc70648.zip NAME=graphics181 ALIGN=BOTTOM WIDTH=155 HEIGHT=23 BORDER=0> . <IMG SRC=dopc70649.zip NAME=graphics182 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> - Називають <a href="Оцінка" title="Оцінка">оцінками</a> або симплексними різницями і знаходять так: елементи стовпця <IMG SRC=dopc70611.zip NAME=graphics183 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> множать на <a href="Відповідь" title="Відповідь">відповідні</a> елементи стовпця <IMG SRC=dopc70651.zip NAME=graphics184 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> , Складають результати і віднімають <IMG SRC=dopc70644.zip NAME=graphics185 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> . Наприклад, <IMG SRC=dopc70653.zip NAME=graphics186 ALIGN=BOTTOM WIDTH=192 HEIGHT=24 BORDER=0> . Оцінки ( <IMG SRC=dopc70649.zip NAME=graphics187 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> ) Базисних змінних завжди дорівнюють нулю. Ознака оптимальності опорного плану полягає в наступному: Опорний план буде оптимальним тоді і тільки тоді, коли всі оцінки <IMG SRC=dopc70655.zip NAME=graphics188 ALIGN=BOTTOM WIDTH=40 HEIGHT=21 BORDER=0> для задачі на max і <IMG SRC=dopc70656.zip NAME=graphics189 ALIGN=BOTTOM WIDTH=40 HEIGHT=21 BORDER=0> для задачі на min. Якщо критерії оптимальності не виконуються, то потрібно перейти до нехудшему опорному плану, тобто виключити з базису деяку змінну і ввести замість неї нову з числа вільних змінних. Змінна, яку потрібно ввести в базис, <a href="Відповідь" title="Відповідь">відповідає</a> тій оцінці <IMG SRC=dopc70649.zip NAME=graphics190 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> , Яка не задовольняє умові оптимальності. Якщо таких оцінок кілька, то серед них вибирають найбільшу за абсолютною величиною і <a href="Відповідь" title="Відповідь">відповідну</a> їй змінну вводять в базис. Стовпець з цієї змінної називають дозволяючим. Для визначення змінної, яку потрібно вивести з базису, чинять так: елементи шпальти У ділять тільки на позитивні елементи дозволяє стовпця і знаходять симплексних відносини <IMG SRC=dopc70658.zip NAME=graphics191 ALIGN=BOTTOM WIDTH=45 HEIGHT=40 BORDER=0> . Вибирають з <IMG SRC=dopc70659.zip NAME=graphics192 ALIGN=BOTTOM WIDTH=16 HEIGHT=24 BORDER=0> найменше. Воно називає ту зміну, яку потрібно ввести в базис. Відповідна рядок таблиці називається роздільною. На перетині дозволяє стовпця і роздільною рядка знаходиться дозволяє елемент. Тепер починаємо заповнювати таку таблицю. Покажемо цей <a href="Процес" title="Процес">процес</a> на конкретному прикладі. Приклад. Вирішити симплексним методом задачу лінійного програмування. <IMG SRC=dopc70660.zip NAME=graphics193 ALIGN=BOTTOM WIDTH=92 HEIGHT=20 BORDER=0> max <IMG SRC=dopc70661.zip NAME=graphics194 ALIGN=BOTTOM WIDTH=79 HEIGHT=103 BORDER=0> Рішення. 1) Наводимо завдання до канонічного виду, тобто з обмежень нерівностей робимо рівності. <IMG SRC=dopc70660.zip NAME=graphics195 ALIGN=BOTTOM WIDTH=92 HEIGHT=20 BORDER=0> max <IMG SRC=dopc70663.zip NAME=graphics196 ALIGN=BOTTOM WIDTH=103 HEIGHT=84 BORDER=0> <IMG SRC=dopc70664.zip NAME=graphics197 ALIGN=BOTTOM WIDTH=89 HEIGHT=24 BORDER=0> 2) Визначаємо базисні перемінні - це <IMG SRC=dopc70665.zip NAME=graphics198 ALIGN=BOTTOM WIDTH=65 HEIGHT=20 BORDER=0> . <IMG SRC=dopc70666.zip ALIGN=LEFT><IMG SRC=dopc70667.zip ALIGN=LEFT> 3) Заповнюємо першу таблицю <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=61><COL WIDTH=47><COL WIDTH=44><COL WIDTH=43><COL WIDTH=44><COL WIDTH=43><COL WIDTH=44><COL WIDTH=44><COL WIDTH=44><COL WIDTH=66><TR VALIGN=TOP><TD WIDTH=61> Базис </TD><TD WIDTH=47> <IMG SRC=dopc70611.zip NAME=graphics199 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> </TD><TD WIDTH=44> У </TD><TD WIDTH=43> 2 </TD><TD WIDTH=44> 3 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=66> <IMG SRC=dopc70615.zip NAME=graphics200 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=61> </TD><TD WIDTH=47> </TD><TD WIDTH=44> </TD><TD WIDTH=43> <IMG SRC=dopc70529.zip NAME=graphics201 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70530.zip NAME=graphics202 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70672.zip NAME=graphics203 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70673.zip NAME=graphics204 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70674.zip NAME=graphics205 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70524.zip NAME=graphics206 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=66> </TD></TR><TR VALIGN=TOP><TD WIDTH=61 HEIGHT=17> <IMG SRC=dopc70672.zip NAME=graphics207 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=47> 0 </TD><TD WIDTH=44> 18 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=44> 3 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=66> <IMG SRC=dopc70677.zip NAME=graphics208 ALIGN=BOTTOM WIDTH=45 HEIGHT=28 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=61 HEIGHT=17> <IMG SRC=dopc70673.zip NAME=graphics209 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=47> 0 </TD><TD WIDTH=44> 16 </COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TD><TD WIDTH=43> 2 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=66> <IMG SRC=dopc70679.zip NAME=graphics210 ALIGN=BOTTOM WIDTH=51 HEIGHT=28 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=61 HEIGHT=17> <IMG SRC=dopc70674.zip NAME=graphics211 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=47> 0 </TD><TD WIDTH=44> 5 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=66> <IMG SRC=dopc70681.zip NAME=graphics212 ALIGN=BOTTOM WIDTH=41 HEIGHT=28 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=61 HEIGHT=17> <IMG SRC=dopc70524.zip NAME=graphics213 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=47> 0 </TD><TD WIDTH=44> 21 </TD><TD WIDTH=43> 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=66> - </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=122 HEIGHT=16> <IMG SRC=dopc70683.zip NAME=graphics214 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70638.zip NAME=graphics215 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> 0 </TD><TD WIDTH=43> <IMG SRC=dopc70639.zip NAME=graphics216 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> - 2 </TD><TD WIDTH=44><IMG SRC=dopc70686.zip ALIGN=LEFT> <IMG SRC=dopc70640.zip NAME=graphics217 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> - 3 </TD><TD WIDTH=43> <IMG SRC=dopc70688.zip NAME=graphics218 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> 0 </TD><TD WIDTH=44> <IMG SRC=dopc70689.zip NAME=graphics219 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> 0 </TD><TD WIDTH=44> <IMG SRC=dopc70690.zip NAME=graphics220 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> 0 </TD><TD WIDTH=44> <IMG SRC=dopc70691.zip NAME=graphics221 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> 0 </TD><TD WIDTH=66> </TD></TR></TABLE></CENTER> Тут <IMG SRC=dopc70692.zip NAME=graphics222 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70693.zip NAME=graphics223 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> не задовольняють умові оптимальності, оскільки вони менше нуля. Вибираємо серед них більше по модулю. Це <IMG SRC=dopc70693.zip NAME=graphics224 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> . Отже, стовпець змінної <IMG SRC=dopc70530.zip NAME=graphics225 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> - Дозволяє. Значить, в новий базис потрібно ввести змінну <IMG SRC=dopc70530.zip NAME=graphics226 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> . Знаходимо <IMG SRC=dopc70697.zip NAME=graphics227 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> : <IMG SRC=dopc70698.zip NAME=graphics228 ALIGN=BOTTOM WIDTH=95 HEIGHT=40 BORDER=0> ; <IMG SRC=dopc70699.zip NAME=graphics229 ALIGN=BOTTOM WIDTH=103 HEIGHT=40 BORDER=0> ; <IMG SRC=dopc70700.zip NAME=graphics230 ALIGN=BOTTOM WIDTH=91 HEIGHT=40 BORDER=0> Найменше з цих чисел - це число 5, що відповідає рядку базисної змінної <IMG SRC=dopc70674.zip NAME=graphics231 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> . Значить, рядок базисної змінної <IMG SRC=dopc70674.zip NAME=graphics232 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> - Роздільна, отже, з базису потрібно вивести змінну <IMG SRC=dopc70674.zip NAME=graphics233 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> . Елемент <IMG SRC=dopc70704.zip NAME=graphics234 ALIGN=BOTTOM WIDTH=20 HEIGHT=20 BORDER=0> = 1 - дозволяє. Новий базис: <IMG SRC=dopc70705.zip NAME=graphics235 ALIGN=BOTTOM WIDTH=67 HEIGHT=20 BORDER=0> . Заповнення такої таблиці починаємо зі шпальт «Базис» і « <IMG SRC=dopc70611.zip NAME=graphics236 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> ». Потім заповнюємо роздільну рядок, розділивши кожен її елемент на дозволяючий, тобто на 1. Всі елементи дозволяє стовпця будуть нулями, крім дозволяє, який завжди дорівнює 1. Стовпці під <IMG SRC=dopc70707.zip NAME=graphics237 ALIGN=BOTTOM WIDTH=49 HEIGHT=20 BORDER=0> переписуємо без зміни, оскільки ці змінні залишилися в базисі. Інші елементи нової таблиці знаходимо за правилом прямокутника. Наприклад, елемент <IMG SRC=dopc70708.zip NAME=graphics238 ALIGN=BOTTOM WIDTH=16 HEIGHT=23 BORDER=0> знайдемо з прямокутника <IMG SRC=dopc70708.zip NAME=graphics239 ALIGN=BOTTOM WIDTH=16 HEIGHT=23 BORDER=0> = <IMG SRC=dopc70710.zip NAME=graphics240 ALIGN=BOTTOM WIDTH=84 HEIGHT=36 BORDER=0> Або елемент <IMG SRC=dopc70711.zip NAME=graphics241 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> = <IMG SRC=dopc70712.zip NAME=graphics242 ALIGN=BOTTOM WIDTH=81 HEIGHT=36 BORDER=0> з прямокутника Оцінки <IMG SRC=dopc70649.zip NAME=graphics243 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> для нової таблиці можна знаходити з цього ж правилу. <IMG SRC=dopc70714.zip ALIGN=LEFT> У цілому, рішення даної задачі симплексним методом у вигляді таблиць буде мати вигляд <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=65><COL WIDTH=49><COL WIDTH=46><COL WIDTH=43><COL WIDTH=44><COL WIDTH=44><COL WIDTH=44><COL WIDTH=44><COL WIDTH=44><COL WIDTH=54><TR VALIGN=TOP><TD WIDTH=65> Базис </TD><TD WIDTH=49> <IMG SRC=dopc70611.zip NAME=graphics244 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> </TD><TD WIDTH=46> У </TD><TD WIDTH=43> 2 </TD><TD WIDTH=44> 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> <IMG SRC=dopc70615.zip NAME=graphics245 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=65> </TD><TD WIDTH=49> </TD><TD WIDTH=46> </TD><TD WIDTH=43> <IMG SRC=dopc70529.zip NAME=graphics246 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70530.zip NAME=graphics247 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70672.zip NAME=graphics248 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70673.zip NAME=graphics249 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70674.zip NAME=graphics250 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=44> <IMG SRC=dopc70524.zip NAME=graphics251 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=54> </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70672.zip NAME=graphics252 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 18 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=44> 3 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> 6 </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70673.zip NAME=graphics253 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 16 </TD><TD WIDTH=43> 2 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> 16 </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70674.zip NAME=graphics254 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 5 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70524.zip NAME=graphics255 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 21 </TD><TD WIDTH=43> 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=54> - </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=128 HEIGHT=14> <IMG SRC=dopc70683.zip NAME=graphics256 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=46> 0 </TD><TD WIDTH=43> - 2 </TD><TD WIDTH=44> - 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> таб. 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70672.zip NAME=graphics257 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 3 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> - 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> 3 </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70673.zip NAME=graphics258 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 11 </TD><TD WIDTH=43> 2 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> - 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> 5,5 </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70530.zip NAME=graphics259 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 3 </TD><TD WIDTH=46> 5 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> - </TD></TR><TR VALIGN=TOP><TD WIDTH=65 HEIGHT=14> <IMG SRC=dopc70524.zip NAME=graphics260 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> 0 </TD><TD WIDTH=46> 21 </TD><TD WIDTH=43> 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 1 </TD><TD WIDTH=54> 7 </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=128 HEIGHT=13> <IMG SRC=dopc70683.zip NAME=graphics261 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=46> 15 </TD><TD WIDTH=43> - 2 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=44> 3 </TD><TD WIDTH=44> 0 </TD><TD WIDTH=54> таб. 2 </TD></TR></TABLE></CENTER><CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=63><COL WIDTH=48><COL WIDTH=45><COL WIDTH=42><COL WIDTH=43><COL WIDTH=48><COL WIDTH=48><COL WIDTH=43><COL WIDTH=43><COL WIDTH=53><TR VALIGN=TOP><TD WIDTH=63> Базис </TD><TD WIDTH=48> <IMG SRC=dopc70611.zip NAME=graphics262 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> </TD><TD WIDTH=45> У </TD><TD WIDTH=42> 2 </TD><TD WIDTH=43> 3 </TD><TD WIDTH=48> 0 </TD><TD WIDTH=48> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> <IMG SRC=dopc70615.zip NAME=graphics263 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=63> </TD><TD WIDTH=48> </TD><TD WIDTH=45> </TD><TD WIDTH=42> <IMG SRC=dopc70529.zip NAME=graphics264 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70530.zip NAME=graphics265 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> <IMG SRC=dopc70672.zip NAME=graphics266 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> <IMG SRC=dopc70673.zip NAME=graphics267 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70674.zip NAME=graphics268 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70524.zip NAME=graphics269 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=53> </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70529.zip NAME=graphics270 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 2 </TD><TD WIDTH=45> 3 </TD><TD WIDTH=42> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> 1 </TD><TD WIDTH=48> 0 </TD><TD WIDTH=43> - 3 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> - </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70673.zip NAME=graphics271 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=45> 5 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> - 2 </TD><TD WIDTH=48> 1 </TD><TD WIDTH=43> 5 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14><IMG SRC=dopc70743.zip ALIGN=LEFT> <IMG SRC=dopc70530.zip NAME=graphics272 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 3 </TD><TD WIDTH=45> 5 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=48> 0 </COL></COL></COL></COL></COL></COL></COL></COL></COL></COL><CENTER><TABLE><TR><TD></TD><TD WIDTH=48> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70524.zip NAME=graphics273 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=45> 12 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> - 3 </TD><TD WIDTH=48> 0 </TD><TD WIDTH=43> 9 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=53> <IMG SRC=dopc70746.zip NAME=graphics274 ALIGN=BOTTOM WIDTH=25 HEIGHT=28 BORDER=0> </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=126 HEIGHT=14> <IMG SRC=dopc70683.zip NAME=graphics275 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=45> 21 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> 2 </TD><TD WIDTH=48> 0 </TD><TD WIDTH=43> - 3 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> таб. 3 </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70529.zip NAME=graphics276 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 2 </TD><TD WIDTH=45> 6 </TD><TD WIDTH=42> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> - 0,2 </TD><TD WIDTH=48> 0,6 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70674.zip NAME=graphics277 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=45> 1 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> - 0,4 </TD><TD WIDTH=48> 0,2 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70530.zip NAME=graphics278 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 3 </TD><TD WIDTH=45> 4 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=48> 0,4 </TD><TD WIDTH=48> - 0,2 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70524.zip NAME=graphics279 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=45> 3 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> 0,6 </TD><TD WIDTH=48> - 1,8 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=53> </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=126 HEIGHT=13> <IMG SRC=dopc70683.zip NAME=graphics280 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=45> 24 </TD><TD WIDTH=42> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=48> 0,8 </TD><TD WIDTH=48> 0,6 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> таб. 4 </TD></TR></TABLE></CENTER><IMG SRC=dopc70714.zip ALIGN=LEFT> Оціночна рядок четвертої таблиці показує, що отриманий оптимальний план, так як всі <IMG SRC=dopc70655.zip NAME=graphics281 ALIGN=BOTTOM WIDTH=40 HEIGHT=21 BORDER=0> . <IMG SRC=dopc70755.zip NAME=graphics282 ALIGN=BOTTOM WIDTH=29 HEIGHT=20 BORDER=0> - Це значення <IMG SRC=dopc70756.zip NAME=graphics283 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> зі стовпця В, тобто <IMG SRC=dopc70757.zip NAME=graphics284 ALIGN=BOTTOM WIDTH=37 HEIGHT=23 BORDER=0> , <IMG SRC=dopc70758.zip NAME=graphics285 ALIGN=BOTTOM WIDTH=35 HEIGHT=23 BORDER=0> , <IMG SRC=dopc70759.zip NAME=graphics286 ALIGN=BOTTOM WIDTH=37 HEIGHT=23 BORDER=0> , <IMG SRC=dopc70760.zip NAME=graphics287 ALIGN=BOTTOM WIDTH=36 HEIGHT=23 BORDER=0> . Вільні (небазисной) змінні <IMG SRC=dopc70761.zip NAME=graphics288 ALIGN=BOTTOM WIDTH=63 HEIGHT=23 BORDER=0> . Отже, <IMG SRC=dopc70755.zip NAME=graphics289 ALIGN=BOTTOM WIDTH=29 HEIGHT=20 BORDER=0> = (6, 4, 0, 0, 1, 3), <IMG SRC=dopc70589.zip NAME=graphics290 ALIGN=BOTTOM WIDTH=28 HEIGHT=20 BORDER=0> = <IMG SRC=dopc70646.zip NAME=graphics291 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> = 24. Примітка: При переході від таблиці до таблиці для контролю порівнюють <IMG SRC=dopc70646.zip NAME=graphics292 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> , Яка повинна бути не менше попереднього для задачі на максимум і не більше попереднього - для задачі на мінімум. При використанні <a href="Симплексного_методу" title="Симплексного методу">симплексного методу</a> можливі наступні випадки. 1) Якщо в оціночній рядку симплекс-таблиці оцінка <IMG SRC=dopc70649.zip NAME=graphics293 ALIGN=BOTTOM WIDTH=19 HEIGHT=21 BORDER=0> = 0 відповідає вільної змінної, то це означає, що ЗЛП має не єдиний оптимальний план. 2) Якщо при переході від одного опорного плану до іншого у вирішуючому стовпці немає позитивних елементів, то це означає, що цільова функція ЗЛП є необмеженою і оптимальних планів не існує. Завдання для самостійної роботи. Визначити оптимальний план завдань, використовуючи симплексний метод розв'язання задач лінійного програмування: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=61><COL WIDTH=172><COL WIDTH=64><COL WIDTH=63><COL WIDTH=188><TR VALIGN=TOP><TD WIDTH=61> а) </TD><TD WIDTH=172> <IMG SRC=dopc70767.zip NAME=graphics294 ALIGN=BOTTOM WIDTH=81 HEIGHT=20 BORDER=0> 				 max <IMG SRC=dopc70768.zip NAME=graphics295 ALIGN=BOTTOM WIDTH=93 HEIGHT=44 BORDER=0> <IMG SRC=dopc70769.zip NAME=graphics296 ALIGN=BOTTOM WIDTH=92 HEIGHT=24 BORDER=0> </TD><TD WIDTH=64> </TD><TD WIDTH=63> б) </TD><TD WIDTH=188> <IMG SRC=dopc70767.zip NAME=graphics297 ALIGN=BOTTOM WIDTH=81 HEIGHT=20 BORDER=0> m in <IMG SRC=dopc70771.zip NAME=graphics298 ALIGN=BOTTOM WIDTH=117 HEIGHT=63 BORDER=0> <IMG SRC=dopc70772.zip NAME=graphics299 ALIGN=BOTTOM WIDTH=92 HEIGHT=24 BORDER=0> </TD></TR></TABLE></CENTER> Поняття двоїстості 1) Симетричні двоїсті задачі Розглянемо завдання виробничого планування. Нехай підприємство має m видів ресурсів обсягом <IMG SRC=dopc70773.zip NAME=graphics300 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> одиниць. Ці <a href="Ресурси" title="Ресурси">ресурси</a> повинні бути використані для випуску n видів продукції. Нехай <IMG SRC=dopc70643.zip NAME=graphics301 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> - <a href="Норма" title="Норма">Норма</a> споживання i-го виду ресурсу на <a href="Виробництво" title="Виробництво">виробництво</a> одиниці j-ої продукції; <IMG SRC=dopc70644.zip NAME=graphics302 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> - Ціна реалізації j-ої продукції; <IMG SRC=dopc70651.zip NAME=graphics303 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> - Обсяг виробництва j-ої продукції, що забезпечує підприємству максимальну виручку. </COL></COL></COL></COL></COL> План виробництва <IMG SRC=dopc70470.zip NAME=graphics304 ALIGN=BOTTOM WIDTH=96 HEIGHT=20 BORDER=0> слід скласти з умови максимізації загальної вартості продукції <IMG SRC=dopc70469.zip NAME=graphics305 ALIGN=BOTTOM WIDTH=136 HEIGHT=20 BORDER=0> при обмеженнях на використання ресурсів <IMG SRC=dopc70779.zip NAME=graphics306 ALIGN=BOTTOM WIDTH=171 HEIGHT=84 BORDER=0> <IMG SRC=dopc70473.zip NAME=graphics307 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70474.zip NAME=graphics308 ALIGN=BOTTOM WIDTH=41 HEIGHT=24 BORDER=0> Або в короткій формі запису <a href="Математика" title="Математика">математична</a> модель задачі має вигляд: <IMG SRC=dopc70782.zip NAME=graphics309 ALIGN=BOTTOM WIDTH=108 HEIGHT=43 BORDER=0> (1) <IMG SRC=dopc70783.zip NAME=graphics310 ALIGN=BOTTOM WIDTH=68 HEIGHT=43 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics311 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> (2) <IMG SRC=dopc70473.zip NAME=graphics312 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70474.zip NAME=graphics313 ALIGN=BOTTOM WIDTH=41 HEIGHT=24 BORDER=0> (3) Задачу (1) - (3) називають вихідної. За вихідними даними завдання (1) - (3) сформуємо іншу <a href="Економіка" title="Економіка">економічну</a> задачу. Припустимо, що підприємству дозволено на його розсуд реалізувати всі зазначені <a href="Ресурси" title="Ресурси">ресурси</a>. Необхідно <a href="Встанови" title="Встанови">встановити</a> ціни на них - <IMG SRC=dopc70787.zip NAME=graphics314 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics315 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> , Користуючись такими міркуваннями: <UL><LI> покупець прагне мінімізувати їх загальну вартість; <LI> підприємство згідно продати за цінами, що дає прибуток не меншу, ніж виручка, яку воно може отримати від реалізації виготовленої продукції. </UL> Ці вимоги можна записати у вигляді такої ЗЛП: <IMG SRC=dopc70789.zip NAME=graphics316 ALIGN=BOTTOM WIDTH=183 HEIGHT=20 BORDER=0> <IMG SRC=dopc70790.zip NAME=graphics317 ALIGN=BOTTOM WIDTH=171 HEIGHT=84 BORDER=0> <IMG SRC=dopc70791.zip NAME=graphics318 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics319 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> Або в короткій формі запису: <IMG SRC=dopc70793.zip NAME=graphics320 ALIGN=BOTTOM WIDTH=104 HEIGHT=41 BORDER=0> (4) <IMG SRC=dopc70794.zip NAME=graphics321 ALIGN=BOTTOM WIDTH=68 HEIGHT=41 BORDER=0> , <IMG SRC=dopc70474.zip NAME=graphics322 ALIGN=BOTTOM WIDTH=41 HEIGHT=24 BORDER=0> (5) <IMG SRC=dopc70791.zip NAME=graphics323 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70478.zip NAME=graphics324 ALIGN=BOTTOM WIDTH=41 HEIGHT=23 BORDER=0> (6) Отриману завдання (4) - (6) називають двоїстою. Змінні <IMG SRC=dopc70787.zip NAME=graphics325 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> називаються подвійними оцінками, або тіньовими цінами. Завдання (1) - (3) і (4) - (6) називають парою взаємно двоїстих симетричних завдань, тому що вони мають наступні властивості: <OL><LI> Якщо в одній задачі шукається максимум цільової функції, то в іншій - мінімум. <LI> Коефіцієнти при змінних в цільовій функції однієї задачі є правими частинами обмежень іншого завдання і, навпаки. <LI> У кожній задачі система обмежень задається у вигляді нерівностей, причому всі вони одного сенсу: якщо завдання на max, то всі нерівності містять знаки « <IMG SRC=dopc70799.zip NAME=graphics326 ALIGN=BOTTOM WIDTH=14 HEIGHT=13 BORDER=0> », Якщо на min, то всі нерівності містять знаки« <IMG SRC=dopc70800.zip NAME=graphics327 ALIGN=BOTTOM WIDTH=14 HEIGHT=13 BORDER=0> ». <LI> Матриці обмежень прямої і двоїстої задач є транспонований один до одного. <LI> Число нерівностей в системі обмежень однієї задачі дорівнює числу змінних іншої задачі. <LI> Умова невід'ємності змінних зберігається в обох завданнях. </OL> Примітка: <a href="Поняття" title="Поняття">Поняття</a> «прямий» і «двоїстої» завдань умовно. 2) Побудова моделі двоїстої задачі Використовуючи властивості (1-6), покажемо на конкретному прикладі побудова двоїстої задачі. Приклад. Нехай вихідна задача має вигляд: <IMG SRC=dopc70801.zip NAME=graphics328 ALIGN=BOTTOM WIDTH=141 HEIGHT=20 BORDER=0> <IMG SRC=dopc70802.zip NAME=graphics329 ALIGN=BOTTOM WIDTH=105 HEIGHT=84 BORDER=0> <IMG SRC=dopc70473.zip NAME=graphics330 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70515.zip NAME=graphics331 ALIGN=BOTTOM WIDTH=39 HEIGHT=24 BORDER=0> Потрібно скласти до неї двоїсту. Рішення. Запишемо розширену матрицю системи обмежень і Транспонуємо її. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=36><COL WIDTH=42><COL WIDTH=36><COL WIDTH=36><COL WIDTH=51><COL WIDTH=1><COL WIDTH=50><COL WIDTH=36><COL WIDTH=36><COL WIDTH=36><COL WIDTH=42><COL WIDTH=48><TR VALIGN=TOP><TD WIDTH=36> </TD><TD WIDTH=42> 1 </TD><TD WIDTH=36> - 1 </TD><TD WIDTH=36> 2 </TD><TD WIDTH=51> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=50> </TD><TD WIDTH=36> 1 </TD><TD WIDTH=36> 2 </TD><TD WIDTH=36> 5 </TD><TD WIDTH=42> 11 </TD><TD WIDTH=48> 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=36> </TD><TD WIDTH=42> 2 </TD><TD WIDTH=36> 1 </TD><TD WIDTH=36> - 3 </TD><TD WIDTH=51> 4 </TD><TD WIDTH=1> </TD><TD WIDTH=50> А Т = </TD><TD WIDTH=36> - 1 </TD><TD WIDTH=36> 1 </TD><TD WIDTH=36> - 1 </TD><TD WIDTH=42> 1 </TD><TD WIDTH=48> 3 </TD></TR><TR VALIGN=TOP><TD WIDTH=36> А = </TD><TD WIDTH=42> 5 </TD><TD WIDTH=36> - 1 </TD><TD WIDTH=36> 1 </TD><TD WIDTH=51> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=50> </TD><TD WIDTH=36> 2 </TD><TD WIDTH=36> - 3 </TD><TD WIDTH=36> 1 </TD><TD WIDTH=42> 2 </TD><TD WIDTH=48> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=36> </TD><TD WIDTH=42> 11 </TD><TD WIDTH=36> 1 </TD><TD WIDTH=36> 2 </TD><TD WIDTH=51> 1 </TD><TD WIDTH=1> </TD><TD WIDTH=50> </TD><TD WIDTH=36> 2 </TD><TD WIDTH=36> 4 </TD><TD WIDTH=36> 3 </TD><TD WIDTH=42> 1 </TD><TD WIDTH=48> min </TD></TR></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TABLE></CENTER></LI></LI></LI></LI></LI></LI></LI></LI><CENTER><TABLE><TR><TD></TD></TR><TR VALIGN=TOP><TD WIDTH=36> </TD><TD WIDTH=42> 2 </TD><TD WIDTH=36> 3 </TD><TD WIDTH=36> 1 </TD><TD WIDTH=51> max </TD><TD WIDTH=1> </TD><TD WIDTH=50> </TD><TD WIDTH=36> </TD><TD WIDTH=36> </TD><TD WIDTH=36> </TD><TD WIDTH=42> </TD><TD WIDTH=48> </TD></TR></TABLE></CENTER> Тепер запишемо двоїсту задачу по А Т з змінними <IMG SRC=dopc70787.zip NAME=graphics332 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70806.zip NAME=graphics333 ALIGN=BOTTOM WIDTH=36 HEIGHT=23 BORDER=0> . <IMG SRC=dopc70807.zip NAME=graphics334 ALIGN=BOTTOM WIDTH=173 HEIGHT=20 BORDER=0> <IMG SRC=dopc70808.zip NAME=graphics335 ALIGN=BOTTOM WIDTH=143 HEIGHT=63 BORDER=0> <IMG SRC=dopc70791.zip NAME=graphics336 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70806.zip NAME=graphics337 ALIGN=BOTTOM WIDTH=36 HEIGHT=23 BORDER=0> . Приклад. До заданої завданню записати двоїсту: <IMG SRC=dopc70811.zip NAME=graphics338 ALIGN=BOTTOM WIDTH=115 HEIGHT=89 BORDER=0> Рішення. Так як завдання на min, то всі нерівності повинні мати знаки « <IMG SRC=dopc70800.zip NAME=graphics339 ALIGN=BOTTOM WIDTH=14 HEIGHT=14 BORDER=0> ». З цією метою друге обмеження помножимо на (-1); при цьому знак нерівності зміниться на протилежний. Тепер завдання буде мати вигляд: <IMG SRC=dopc70813.zip NAME=graphics340 ALIGN=BOTTOM WIDTH=115 HEIGHT=20 BORDER=0> <IMG SRC=dopc70814.zip NAME=graphics341 ALIGN=BOTTOM WIDTH=96 HEIGHT=44 BORDER=0> <IMG SRC=dopc70473.zip NAME=graphics342 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70572.zip NAME=graphics343 ALIGN=BOTTOM WIDTH=40 HEIGHT=24 BORDER=0> Запишемо <a href="Матриці" title="Матриці">матриці</a> А і А Т. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=55><COL WIDTH=54><COL WIDTH=54><COL WIDTH=72><COL WIDTH=1><COL WIDTH=73><COL WIDTH=54><COL WIDTH=54><COL WIDTH=74><TR VALIGN=TOP><TD WIDTH=55> </TD><TD WIDTH=54> 1 </TD><TD WIDTH=54> 1 </TD><TD WIDTH=72> 1 </TD><TD WIDTH=1> </TD><TD WIDTH=73> </TD><TD WIDTH=54> 1 </TD><TD WIDTH=54> - 2 </TD><TD WIDTH=74> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=55> А = </TD><TD WIDTH=54> - 2 </TD><TD WIDTH=54> - 3 </TD><TD WIDTH=72> - 5 </TD><TD WIDTH=1> </TD><TD WIDTH=73> А Т = </TD><TD WIDTH=54> 1 </TD><TD WIDTH=54> - 3 </TD><TD WIDTH=74> 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=55> </TD><TD WIDTH=54> 5 </TD><TD WIDTH=54> 2 </TD><TD WIDTH=72> min </TD><TD WIDTH=1> </TD><TD WIDTH=73> </TD><TD WIDTH=54> 1 </TD><TD WIDTH=54> - 5 </TD><TD WIDTH=74> max </TD></TR></TABLE></CENTER> Двоїста задача: <IMG SRC=dopc70817.zip NAME=graphics344 ALIGN=BOTTOM WIDTH=112 HEIGHT=20 BORDER=0> <IMG SRC=dopc70818.zip NAME=graphics345 ALIGN=BOTTOM WIDTH=75 HEIGHT=44 BORDER=0> <IMG SRC=dopc70791.zip NAME=graphics346 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70820.zip NAME=graphics347 ALIGN=BOTTOM WIDTH=36 HEIGHT=23 BORDER=0> . 3) Застосування теорем подвійності до аналізу оптимальних рішень пари симетричних двоїстих задач Розглянемо таку задачу. Підприємство планує випускати 3 види продукції - П 1, П 2, П 3. Для цього воно має в своєму розпорядженні обсягами ресурсів 3-х видів Р 1, Р 2, Р 3. Витрати кожного ресурсу на виготовлення одиниці продукції і ціна одиниці продукції наведені в таблиці: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=108><COL WIDTH=108><COL WIDTH=108><COL WIDTH=108><COL WIDTH=115><TR VALIGN=TOP><TD WIDTH=108 HEIGHT=11> П j Р i </TD><TD WIDTH=108> П 1 </TD><TD WIDTH=108> П 2 </TD><TD WIDTH=108> П 3 </TD><TD WIDTH=115> Обсяг <IMG SRC=dopc70773.zip NAME=graphics348 ALIGN=BOTTOM WIDTH=13 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=108 HEIGHT=12> Р 1 </TD><TD WIDTH=108> 4 </TD><TD WIDTH=108> 2 </TD><TD WIDTH=108> 1 </TD><TD WIDTH=115> 180 </TD></TR><TR VALIGN=TOP><TD WIDTH=108 HEIGHT=12> Р 2 </TD><TD WIDTH=108> 3 </TD><TD WIDTH=108> 1 </TD><TD WIDTH=108> 1 </TD><TD WIDTH=115> 210 </TD></TR><TR VALIGN=TOP><TD WIDTH=108 HEIGHT=12> Р 3 </TD><TD WIDTH=108> 1 </TD><TD WIDTH=108> 2 </TD><TD WIDTH=108> 5 </TD><TD WIDTH=115> 244 </TD></TR><TR VALIGN=TOP><TD WIDTH=108 HEIGHT=11> Ціна <IMG SRC=dopc70644.zip NAME=graphics349 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> </TD><TD WIDTH=108> 10 </TD><TD WIDTH=108> 14 </TD><TD WIDTH=108> 12 </TD><TD WIDTH=115> </TD></TR></TABLE></CENTER> Потрібно: <OL><LI> побудувати модель вихідної і двоїстої задач; <LI> вирішити вихідну задачу симплексним методом; <LI> знайти оптимальне рішення двоїстої задачі, використовуючи перевірочну рядок останньої симплексного таблиці; <LI> дати <a href="Економічний_аналіз" title="Економічний аналіз">економічний аналіз</a> основних і додаткових змінним оптимальних рішень обох завдань; <LI> у відповіді записати оптимальні рішення обох задач і значення їх цільових функцій; вказати найбільш дефіцитний ресурс і найбільш збитковий вид продукції. </OL> Рішення. 1. Побудуємо модель вихідної задачі <IMG SRC=dopc70823.zip NAME=graphics350 ALIGN=BOTTOM WIDTH=164 HEIGHT=20 BORDER=0> <IMG SRC=dopc70824.zip NAME=graphics351 ALIGN=BOTTOM WIDTH=117 HEIGHT=63 BORDER=0> <IMG SRC=dopc70473.zip NAME=graphics352 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70515.zip NAME=graphics353 ALIGN=BOTTOM WIDTH=39 HEIGHT=24 BORDER=0> . Тут х 1, х 2, х 3 - план випуску продукції. Складемо математичну модель двоїстої задачі: <IMG SRC=dopc70827.zip NAME=graphics354 ALIGN=BOTTOM WIDTH=188 HEIGHT=20 BORDER=0> </LI></LI></LI></LI></LI></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL> <IMG SRC=dopc70828.zip NAME=graphics355 ALIGN=BOTTOM WIDTH=112 HEIGHT=63 BORDER=0> <IMG SRC=dopc70791.zip NAME=graphics356 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70830.zip NAME=graphics357 ALIGN=BOTTOM WIDTH=36 HEIGHT=21 BORDER=0> . 2. Вирішимо вихідну задачу симплексним методом. Запишемо її канонічний вигляд: <IMG SRC=dopc70823.zip NAME=graphics358 ALIGN=BOTTOM WIDTH=164 HEIGHT=20 BORDER=0> <IMG SRC=dopc70832.zip NAME=graphics359 ALIGN=BOTTOM WIDTH=141 HEIGHT=63 BORDER=0> <IMG SRC=dopc70473.zip NAME=graphics360 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70528.zip NAME=graphics361 ALIGN=BOTTOM WIDTH=39 HEIGHT=24 BORDER=0> . <IMG SRC=dopc70714.zip ALIGN=LEFT> х 4, х 5, х 6 - додаткові і вони ж базисні змінні. Початковий опорний план <IMG SRC=dopc70836.zip NAME=graphics362 ALIGN=BOTTOM WIDTH=44 HEIGHT=21 BORDER=0> (0, 0, 0; 180; 210; 244). <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=63><COL WIDTH=48><COL WIDTH=52><COL WIDTH=45><COL WIDTH=45><COL WIDTH=45><COL WIDTH=43><COL WIDTH=43><COL WIDTH=43><COL WIDTH=53><TR VALIGN=TOP><TD WIDTH=63> Базис </TD><TD WIDTH=48> <IMG SRC=dopc70611.zip NAME=graphics363 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> </TD><TD WIDTH=52> У </TD><TD WIDTH=45> 10 </TD><TD WIDTH=45> 14 </TD><TD WIDTH=45> 12 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> <IMG SRC=dopc70615.zip NAME=graphics364 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=63> </TD><TD WIDTH=48> </TD><TD WIDTH=52> </TD><TD WIDTH=45> <IMG SRC=dopc70529.zip NAME=graphics365 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=45> <IMG SRC=dopc70530.zip NAME=graphics366 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=45> <IMG SRC=dopc70672.zip NAME=graphics367 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70673.zip NAME=graphics368 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70674.zip NAME=graphics369 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70524.zip NAME=graphics370 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=53> </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70673.zip NAME=graphics371 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=52> 180 </TD><TD WIDTH=45> 4 </TD><TD WIDTH=45> 2 </TD><TD WIDTH=45> 1 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> 90 </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70674.zip NAME=graphics372 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=52> 210 </TD><TD WIDTH=45> 3 </TD><TD WIDTH=45> 1 </TD><TD WIDTH=45> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> 210 </TD></TR><TR VALIGN=TOP><TD WIDTH=63 HEIGHT=14> <IMG SRC=dopc70524.zip NAME=graphics373 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=48> 0 </TD><TD WIDTH=52> 244 </TD><TD WIDTH=45> 1 </TD><TD WIDTH=45> 2 </TD><TD WIDTH=45> 5 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=53> 122 </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=125 HEIGHT=13> <IMG SRC=dopc70683.zip NAME=graphics374 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=52> 0 </TD><TD WIDTH=45> - 10 </TD><TD WIDTH=45> - 14 </TD><TD WIDTH=45> - 12 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=53> таб. 1 </TD></TR></TABLE></CENTER><CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=56><COL WIDTH=43><COL WIDTH=52><COL WIDTH=55><COL WIDTH=40><COL WIDTH=43><COL WIDTH=55><COL WIDTH=40><COL WIDTH=49><COL WIDTH=47><TR VALIGN=TOP><TD WIDTH=56> Базис </TD><TD WIDTH=43> <IMG SRC=dopc70611.zip NAME=graphics375 ALIGN=BOTTOM WIDTH=23 HEIGHT=24 BORDER=0> </TD><TD WIDTH=52> У </TD><TD WIDTH=55> 10 </TD><TD WIDTH=40> 14 </TD><TD WIDTH=43> 12 </TD><TD WIDTH=55> 0 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> 0 </TD><TD WIDTH=47> <IMG SRC=dopc70615.zip NAME=graphics376 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=56> </TD><TD WIDTH=43> </TD><TD WIDTH=52> </TD><TD WIDTH=55> <IMG SRC=dopc70529.zip NAME=graphics377 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=40> <IMG SRC=dopc70530.zip NAME=graphics378 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70672.zip NAME=graphics379 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> <IMG SRC=dopc70673.zip NAME=graphics380 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=40> <IMG SRC=dopc70674.zip NAME=graphics381 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> <IMG SRC=dopc70524.zip NAME=graphics382 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=47> </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=14> <IMG SRC=dopc70530.zip NAME=graphics383 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> 14 </TD><TD WIDTH=52> 90 </TD><TD WIDTH=55> 2 </TD><TD WIDTH=40> 1 </TD><TD WIDTH=43> 0,5 </TD><TD WIDTH=55> 0,5 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> 0 </TD><TD WIDTH=47> 180 </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=14> <IMG SRC=dopc70674.zip NAME=graphics384 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> 0 </TD><TD WIDTH=52> 120 </TD><TD WIDTH=55> 1 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=43> 0,5 </TD><TD WIDTH=55> - 0,5 </TD><TD WIDTH=40> 1 </TD><TD WIDTH=49> 0 </TD><TD WIDTH=47> 240 </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=14> <IMG SRC=dopc70524.zip NAME=graphics385 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> 0 </COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TD></TR></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TABLE></CENTER><CENTER><TABLE><TR><TD></TD><TD WIDTH=52> 64 </TD><TD WIDTH=55> - 3 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=43> 4 </TD><TD WIDTH=55> - 1 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> 1 </TD><TD WIDTH=47> 16 </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=113 HEIGHT=14> <IMG SRC=dopc70683.zip NAME=graphics386 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=52> 1260 </TD><TD WIDTH=55> 18 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=43> - 5 </TD><TD WIDTH=55> 7 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> 0 </TD><TD WIDTH=47> таб. 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=14> <IMG SRC=dopc70530.zip NAME=graphics387 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> 14 </TD><TD WIDTH=52> 82 </TD><TD WIDTH=55> 2,375 </TD><TD WIDTH=40> 1 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=55> 0,625 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> - 0,125 </TD><TD WIDTH=47> </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=14> <IMG SRC=dopc70674.zip NAME=graphics388 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> 0 </TD><TD WIDTH=52> 80 </TD><TD WIDTH=55> 1,375 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=55> 0,125 </TD><TD WIDTH=40> 1 </TD><TD WIDTH=49> - 0,625 </TD><TD WIDTH=47> </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=14> <IMG SRC=dopc70672.zip NAME=graphics389 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> 12 </TD><TD WIDTH=52> 16 </TD><TD WIDTH=55> - 0,75 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=43> 1 </TD><TD WIDTH=55> - 0,25 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> 0,25 </TD><TD WIDTH=47> </TD></TR><TR VALIGN=TOP><TD COLSPAN=2 WIDTH=113 HEIGHT=14> <IMG SRC=dopc70683.zip NAME=graphics390 ALIGN=BOTTOM WIDTH=72 HEIGHT=17 BORDER=0> </TD><TD WIDTH=52> 1340 </TD><TD WIDTH=55> 14,25 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=43> 0 </TD><TD WIDTH=55> 5,75 </TD><TD WIDTH=40> 0 </TD><TD WIDTH=49> 1,25 </TD><TD WIDTH=47> таб. 3 </TD></TR><TR VALIGN=TOP><TD WIDTH=56 HEIGHT=8> </TD><TD WIDTH=43> </TD><TD WIDTH=52> </TD><TD WIDTH=55> <IMG SRC=dopc70639.zip NAME=graphics391 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=40> <IMG SRC=dopc70640.zip NAME=graphics392 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=43> <IMG SRC=dopc70688.zip NAME=graphics393 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=55> <IMG SRC=dopc70689.zip NAME=graphics394 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=40> <IMG SRC=dopc70690.zip NAME=graphics395 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=49> <IMG SRC=dopc70691.zip NAME=graphics396 ALIGN=BOTTOM WIDTH=19 HEIGHT=20 BORDER=0> </TD><TD WIDTH=47> </TD></TR></TABLE></CENTER> Так як всі оцінки <IMG SRC=dopc70655.zip NAME=graphics397 ALIGN=BOTTOM WIDTH=40 HEIGHT=21 BORDER=0> , То отриманий оптимальний план: <IMG SRC=dopc70755.zip NAME=graphics398 ALIGN=BOTTOM WIDTH=29 HEIGHT=20 BORDER=0> = (0; 82; 16; 0; 80; 0); <IMG SRC=dopc70873.zip NAME=graphics399 ALIGN=BOTTOM WIDTH=28 HEIGHT=20 BORDER=0> = 1340. 3. Знайдемо оптимальне рішення двоїстої задачі, використовуючи останню перевірочну рядок симплексного таблиці і співвідношення між змінними прямої і двоїстої задач. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=88><COL WIDTH=89><COL WIDTH=89><COL WIDTH=89><COL WIDTH=89><COL WIDTH=88><TR VALIGN=TOP><TD COLSPAN=3 WIDTH=295 HEIGHT=5><IMG SRC=dopc70874.zip ALIGN=LEFT> основні 				 змінні </TD><TD COLSPAN=3 WIDTH=295> додаткові змінні </TD></TR><TR VALIGN=TOP><TD WIDTH=88 HEIGHT=6> <IMG SRC=dopc70529.zip NAME=graphics400 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70530.zip NAME=graphics401 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70672.zip NAME=graphics402 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70673.zip NAME=graphics403 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70674.zip NAME=graphics404 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=88> <IMG SRC=dopc70524.zip NAME=graphics405 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=88 HEIGHT=6> </TD><TD WIDTH=89> </TD><TD WIDTH=89> </TD><TD WIDTH=89> </TD><TD WIDTH=89> </TD><TD WIDTH=88> </TD></TR><TR VALIGN=TOP><TD WIDTH=88 HEIGHT=6> <IMG SRC=dopc70881.zip NAME=graphics406 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70882.zip NAME=graphics407 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70883.zip NAME=graphics408 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70884.zip NAME=graphics409 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD><TD WIDTH=89> <IMG SRC=dopc70885.zip NAME=graphics410 ALIGN=BOTTOM WIDTH=17 HEIGHT=20 BORDER=0> </TD><TD WIDTH=88> <IMG SRC=dopc70886.zip NAME=graphics411 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD COLSPAN=3 WIDTH=295 HEIGHT=5> додаткові змінні </TD><TD COLSPAN=3 WIDTH=295> основні змінні </TD></TR></TABLE></CENTER> Звідки: <IMG SRC=dopc70887.zip NAME=graphics412 ALIGN=BOTTOM WIDTH=56 HEIGHT=23 BORDER=0> 5,75; <IMG SRC=dopc70888.zip NAME=graphics413 ALIGN=BOTTOM WIDTH=56 HEIGHT=23 BORDER=0> 0; <IMG SRC=dopc70889.zip NAME=graphics414 ALIGN=BOTTOM WIDTH=56 HEIGHT=23 BORDER=0> 1,25; <IMG SRC=dopc70890.zip NAME=graphics415 ALIGN=BOTTOM WIDTH=55 HEIGHT=23 BORDER=0> 14,25; <IMG SRC=dopc70891.zip NAME=graphics416 ALIGN=BOTTOM WIDTH=56 HEIGHT=23 BORDER=0> 0; <IMG SRC=dopc70892.zip NAME=graphics417 ALIGN=BOTTOM WIDTH=56 HEIGHT=23 BORDER=0> 0. <IMG SRC=dopc70893.zip NAME=graphics418 ALIGN=BOTTOM WIDTH=25 HEIGHT=20 BORDER=0> = (5,75; 0; 1,25; 14,25; 0; 0); <IMG SRC=dopc70894.zip NAME=graphics419 ALIGN=BOTTOM WIDTH=203 HEIGHT=20 BORDER=0> 1340. Таким чином отримали <IMG SRC=dopc70873.zip NAME=graphics420 ALIGN=BOTTOM WIDTH=28 HEIGHT=20 BORDER=0> = <IMG SRC=dopc70896.zip NAME=graphics421 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> 1340. 4. Проаналізуємо основні і додаткові змінні оптимальних рішень обох завдань. Основні змінні вихідної задачі - це планований випуск продукції. <IMG SRC=dopc70897.zip NAME=graphics422 ALIGN=BOTTOM WIDTH=68 HEIGHT=63 BORDER=0> Продукцію І-го виду до випуску не планують, ІІ-го виду - у кількості 82 од. та ІІІ-го виду - у кількості 16 од. Додаткові змінні вихідної задачі показують залишки сировини. <IMG SRC=dopc70898.zip NAME=graphics423 ALIGN=BOTTOM WIDTH=68 HEIGHT=63 BORDER=0> </COL></COL></COL></COL></COL></COL> Сировина І та ІІІ видів витрачено повністю. А сировина ІІ виду залишилося в кількості 80 од. Основні змінні двоїстої задачі характеризують дефіцитність сировини: якщо <IMG SRC=dopc70899.zip NAME=graphics424 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , То сировина дефіцитне; якщо <IMG SRC=dopc70900.zip NAME=graphics425 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , То сировина недефіцитні. <IMG SRC=dopc70901.zip NAME=graphics426 ALIGN=BOTTOM WIDTH=79 HEIGHT=63 BORDER=0> Таким чином, сировина І та ІІІ видів дефіцитне, причому найбільш дефіцитний сировину І-го виду. Сировина ІІ виду недефіцитні. Додаткові змінні двоїстої задачі характеризують рентабельність продукції. При цьому, якщо <IMG SRC=dopc70899.zip NAME=graphics427 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , То продукція нерентабельна. <IMG SRC=dopc70903.zip NAME=graphics428 ALIGN=BOTTOM WIDTH=84 HEIGHT=63 BORDER=0> За цим співвідношенням видно, що продукція І виду нерентабельна, а ІІ і ІІІ - рентабельна. Відповідь: <IMG SRC=dopc70755.zip NAME=graphics429 ALIGN=BOTTOM WIDTH=29 HEIGHT=20 BORDER=0> = (0; 82; 16; 0; 80; 0); <IMG SRC=dopc70873.zip NAME=graphics430 ALIGN=BOTTOM WIDTH=28 HEIGHT=20 BORDER=0> = 1340; <IMG SRC=dopc70893.zip NAME=graphics431 ALIGN=BOTTOM WIDTH=25 HEIGHT=20 BORDER=0> = (5,75; 0; 1,25; 14,25; 0; 0); <IMG SRC=dopc70896.zip NAME=graphics432 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> 1340 Найбільш дефіцитне сировину І виду. Найбільш збитковий І вид продукції. Завдання для самостійної роботи. Для виробництва чотирьох видів продукції (П 1, П 2, П 3, П 4) використовуються три види ресурсів. Норма витрат ресурсів, використаних для випуску одиниці продукції кожного виду, ціна одиниці продукції і запаси ресурсів наведено в таблиці. Побудувати модель прямої і двоїстої задач. Знайти оптимальний план для обох задач і екстремальні значення цільових функцій. Дати економічну інтерпретацію основним і додатковим змінним вихідної і двоїстої задач. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=117><COL WIDTH=75><COL WIDTH=75><COL WIDTH=75><COL WIDTH=75><COL WIDTH=118><TR VALIGN=TOP><TD WIDTH=117> Ресурси Продукція </TD><TD COLSPAN=4 WIDTH=341> Витрати ресурсів на одиницю продукції </TD><TD WIDTH=118> Обсяг ресурсів </TD></TR><TR VALIGN=TOP><TD WIDTH=117> </TD><TD WIDTH=75> П 1 </TD><TD WIDTH=75> П 2 </TD><TD WIDTH=75> П 3 </TD><TD WIDTH=75> П 4 </TD><TD WIDTH=118> </TD></TR><TR VALIGN=TOP><TD WIDTH=117> Р 1 </TD><TD WIDTH=75> 2 </TD><TD WIDTH=75> 3 </TD><TD WIDTH=75> 4 </TD><TD WIDTH=75> 4 </TD><TD WIDTH=118> 2100 </TD></TR><TR VALIGN=TOP><TD WIDTH=117> Р 2 </TD><TD WIDTH=75> 5 </TD><TD WIDTH=75> 5 </TD><TD WIDTH=75> 0 </TD><TD WIDTH=75> 7 </TD><TD WIDTH=118> 2800 </TD></TR><TR VALIGN=TOP><TD WIDTH=117> Р 3 </TD><TD WIDTH=75> 8 </TD><TD WIDTH=75> 7 </TD><TD WIDTH=75> 10 </TD><TD WIDTH=75> 9 </TD><TD WIDTH=118> 3000 </TD></TR><TR VALIGN=TOP><TD WIDTH=117> Ціна одиниці </TD><TD WIDTH=75> 60 </TD><TD WIDTH=75> 65 </TD><TD WIDTH=75> 55 </TD><TD WIDTH=75> 62 </TD><TD WIDTH=118> </TD></TR></TABLE></CENTER> Транспортна задача (ТЗ) Транспортна задача виникає при плануванні раціональних перевезень вантажів. Математична модель <a href="Транспорт" title="Транспорт">транспортної</a> задачі в <a href="Найпростіші" title="Найпростіші">найпростішому</a> випадку має вигляд: <IMG SRC=dopc70908.zip NAME=graphics433 ALIGN=BOTTOM WIDTH=100 HEIGHT=43 BORDER=0> max (1) <IMG SRC=dopc70909.zip NAME=graphics434 ALIGN=BOTTOM WIDTH=125 HEIGHT=87 BORDER=0> (2) <IMG SRC=dopc70910.zip NAME=graphics435 ALIGN=BOTTOM WIDTH=37 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70911.zip NAME=graphics436 ALIGN=BOTTOM WIDTH=44 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70912.zip NAME=graphics437 ALIGN=BOTTOM WIDTH=40 HEIGHT=23 BORDER=0> (3) Тут: <IMG SRC=dopc70913.zip NAME=graphics438 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> - Запаси постачальників; <IMG SRC=dopc70914.zip NAME=graphics439 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> - Попит споживачів; <IMG SRC=dopc70915.zip NAME=graphics440 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> - Тарифи, тобто вартості перевезення одиниці вантажу від <IMG SRC=dopc70916.zip NAME=graphics441 ALIGN=BOTTOM WIDTH=9 HEIGHT=16 BORDER=0> -Го постачальника до <IMG SRC=dopc70917.zip NAME=graphics442 ALIGN=BOTTOM WIDTH=12 HEIGHT=19 BORDER=0> -Му споживачеві; Z - <a href="Транспорт" title="Транспорт">транспортні</a> витрати; <IMG SRC=dopc70918.zip NAME=graphics443 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> - Кількість продукту, що перевозиться від <IMG SRC=dopc70916.zip NAME=graphics444 ALIGN=BOTTOM WIDTH=9 HEIGHT=16 BORDER=0> -Го постачальника до <IMG SRC=dopc70917.zip NAME=graphics445 ALIGN=BOTTOM WIDTH=12 HEIGHT=19 BORDER=0> -Му споживачеві. Зазвичай <a href="Транспорт" title="Транспорт">транспортну</a> задачу задають трьома матрицями: <a href="Матриці" title="Матриці">матрицею</a> постачальників, матрицею споживачів і матрицею тарифів. Для наочності транспортну задачу представляють у вигляді розподільчої таблиці. Будь-яка <a href="Транспортна_задача" title="Транспортна задача">транспортна задача</a> має допустиме рішення (матрицю перевезень <IMG SRC=dopc70921.zip NAME=graphics446 ALIGN=BOTTOM WIDTH=25 HEIGHT=25 BORDER=0> ), Якщо <IMG SRC=dopc70922.zip NAME=graphics447 ALIGN=BOTTOM WIDTH=75 HEIGHT=43 BORDER=0> (4) Якщо умова (4) виконується, то транспортну задачу називають транспортної завданням закритого типу. Допустиме <a href="Рішення_транспортної_задачі" title="Рішення транспортної задачі">рішення транспортної задачі</a> часто називають планом перевезень. 1) Побудова початкового опорного плану. Його вирожденність або невирожденості. Ранг <a href="Матриці" title="Матриці">матриці</a> системи. а) Метод північно-західного кута. Заповнення розподільчої таблиці починають з клітини (1; 1), при цьому <IMG SRC=dopc70923.zip NAME=graphics448 ALIGN=BOTTOM WIDTH=88 HEIGHT=20 BORDER=0> . Далі зміщуються або по рядку вправо або за стовпцем вниз до клітини <IMG SRC=dopc70924.zip NAME=graphics449 ALIGN=BOTTOM WIDTH=43 HEIGHT=20 BORDER=0> . Заповнені клітини повинні поширюватися так, щоб їх можна було з'єднати ламаною лінією, ланки якої взаємно <a href="Перпендикуляр" title="Перпендикуляр">перпендикулярні</a>. Приклад. Побудувати методом північно-західного кута початковий опорний план для транспортної задачі: постачальники а = (20; 30; 40); споживачі <IMG SRC=dopc70925.zip NAME=graphics450 ALIGN=BOTTOM WIDTH=12 HEIGHT=17 BORDER=0> = (15; 35; 20; 20); тарифи перевезень <IMG SRC=dopc70926.zip NAME=graphics451 ALIGN=BOTTOM WIDTH=99 HEIGHT=63 BORDER=0> </COL></COL></COL></COL></COL></COL> Знайти вартість перевезень. Рішення. Будуємо розподільну таблицю і знаходимо вантаж х 11 = min (20, 15) = 15. За одну колонку не переміщається, тому що попит І споживача задоволений. Переміщаємося за І рядку в клітку (1, 2): х 12 = min (а 1 - х 11; b 2) = min (5, 35) = 5. Тепер переходимо за ІІ стовпцю в клітину (2, 2): х 22 = min (30; b 2 - х 12) = min (30, 30) = 30. Так як попит ІІ споживача задоволений і у ІІ постачальника продукція вже вибрана, то переходимо до клітини (3, 3): х 33 = min (40; 20) = 20. х 34 = min (а 3 - х 33; b 4) = min (20; 20) = 20. Таким чином, отриманий план перевезень: <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=90><COL WIDTH=39><COL WIDTH=57><COL WIDTH=39><COL WIDTH=57><COL WIDTH=39><COL WIDTH=66><COL WIDTH=39><COL WIDTH=65><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=24> <IMG SRC=dopc70914.zip NAME=graphics452 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> <IMG SRC=dopc70928.zip NAME=graphics453 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD COLSPAN=2 WIDTH=110> 15 </TD><TD COLSPAN=2 WIDTH=110> 35 </TD><TD COLSPAN=2 WIDTH=119> 20 </TD><TD COLSPAN=2 WIDTH=118> 20 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=1> 20 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 4 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 6 </TD><TD WIDTH=39> </TD><TD WIDTH=66> 12 </TD><TD WIDTH=39> </TD><TD WIDTH=65> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=110> 15 </TD><TD COLSPAN=2 WIDTH=110> 5 </TD><TD COLSPAN=2 WIDTH=119> </TD><TD COLSPAN=2 WIDTH=118> </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=1> 30 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 2 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 7 </TD><TD WIDTH=39> </TD><TD WIDTH=66> 8 </TD><TD WIDTH=39> </TD><TD WIDTH=65> 10 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=110> 30 </TD><TD COLSPAN=2 WIDTH=119> </TD><TD COLSPAN=2 WIDTH=118> </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=1> 40 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 5 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 3 </TD><TD WIDTH=39> </TD><TD WIDTH=66> 4 </TD><TD WIDTH=39> </TD><TD WIDTH=65> 6 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=8> </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=119> 20 </TD><TD COLSPAN=2 WIDTH=118> 20 </TD></TR></TABLE></CENTER> Для підрахунку вартості перевезень потрібно кількість вантажу в кожній заповненої клітці помножити на відповідний тариф в цій клітці і результати скласти. <IMG SRC=dopc70929.zip NAME=graphics454 ALIGN=BOTTOM WIDTH=232 HEIGHT=16 BORDER=0> . б) Метод мінімального елемента (найменшої вартості). Будуємо розподільну таблицю і починаємо її заповнювати з тієї клітини, в якій найменший тариф. Приклад. Побудувати початковий опорний план методом мінімальної вартості і знайти <a href="Транспорт" title="Транспорт">транспортні</a> витрати для транспортної задачі: постачальники а = (20; 30; 40); споживачі <IMG SRC=dopc70925.zip NAME=graphics455 ALIGN=BOTTOM WIDTH=12 HEIGHT=17 BORDER=0> = (15; 35; 20; 20); тарифи перевезень <IMG SRC=dopc70926.zip NAME=graphics456 ALIGN=BOTTOM WIDTH=99 HEIGHT=63 BORDER=0> Рішення. Будуємо розподільну таблицю і починаємо її заповнювати з клітини (2; 1), оскільки в ній найменший тариф х 21 = min (30, 15) = 15. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=90><COL WIDTH=39><COL WIDTH=57><COL WIDTH=39><COL WIDTH=57><COL WIDTH=39><COL WIDTH=66><COL WIDTH=39><COL WIDTH=65><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=24> <IMG SRC=dopc70914.zip NAME=graphics457 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> <IMG SRC=dopc70928.zip NAME=graphics458 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD COLSPAN=2 WIDTH=110> 15 </TD><TD COLSPAN=2 WIDTH=110> 35 </TD><TD COLSPAN=2 WIDTH=119> 20 </TD><TD COLSPAN=2 WIDTH=118> 20 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=1> 20 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 4 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 6 </TD><TD WIDTH=39> </TD><TD WIDTH=66> 12 </TD><TD WIDTH=39> </TD><TD WIDTH=65> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=119> </TD><TD COLSPAN=2 WIDTH=118> 20 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=1> 30 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 2 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 7 </TD><TD WIDTH=39> </TD><TD WIDTH=66> 8 </TD><TD WIDTH=39> </TD><TD WIDTH=65> 10 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=110> 15 </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=119> 15 </TD><TD COLSPAN=2 WIDTH=118> </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=1> 40 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 5 </TD><TD WIDTH=39> </TD><TD WIDTH=57> 3 </TD><TD WIDTH=39> </TD><TD WIDTH=66> 4 </TD><TD WIDTH=39> </TD><TD WIDTH=65> 6 </TD></TR><TR VALIGN=TOP><TD WIDTH=90 HEIGHT=8> </TD><TD COLSPAN=2 WIDTH=110> </TD><TD COLSPAN=2 WIDTH=110> 35 </TD><TD COLSPAN=2 WIDTH=119> 5 </TD><TD COLSPAN=2 WIDTH=118> </TD></TR></TABLE></CENTER> Потім заповнюємо клітину (3, 2) з тарифом з 32 = 3; х 32 = min (40, 35) = 35. Далі х 33 = min (а 3 - х 32; b 3) = (5; 20) = 5; х 14 = min (20; 20) = 20; </COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL> х 23 = min (а 2 - х 21; b 3 - х 33) = min (15, 15) = 15. <IMG SRC=dopc70934.zip NAME=graphics459 ALIGN=BOTTOM WIDTH=229 HEIGHT=16 BORDER=0> . Порівнюючи значення Z в а) і б), бачимо, що з огляду на вартості перевезень,<a href="Витрати" title="Витрати"> витрати</a> при другому методі значно менше. Рангом матриці системи (2) називають число <IMG SRC=dopc70935.zip NAME=graphics460 ALIGN=BOTTOM WIDTH=69 HEIGHT=16 BORDER=0> , Тобто кількість рядків плюс кількість шпальт і мінус одиниця. Якщо число заповнених клітин в розподільній таблиці одно рангом матриці, то отриманий план називається не виродженим. У протилежному випадку - виродженим. У пунктах а) і б) <IMG SRC=dopc70936.zip NAME=graphics461 ALIGN=BOTTOM WIDTH=144 HEIGHT=16 BORDER=0> , А число заповнених клітин 5. Отже, отримані плани - вироджені. 2) Метод потенціалів. Ознака оптимальності опорного плану. Допустиме рішення транспортної задачі є оптимальним тоді і тільки тоді, коли можна знайти такі числа - потенціали <IMG SRC=dopc70937.zip NAME=graphics462 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70938.zip NAME=graphics463 ALIGN=BOTTOM WIDTH=47 HEIGHT=24 BORDER=0> і <IMG SRC=dopc70939.zip NAME=graphics464 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> , <IMG SRC=dopc70940.zip NAME=graphics465 ALIGN=BOTTOM WIDTH=47 HEIGHT=24 BORDER=0> , Які задовольняють таким умовам: <OL TYPE=I><LI><LI> <IMG SRC=dopc70941.zip NAME=graphics466 ALIGN=BOTTOM WIDTH=63 HEIGHT=21 BORDER=0> для всіх заповнених клітин; (5) <LI> <IMG SRC=dopc70942.zip NAME=graphics467 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> для всіх порожніх клітин. (6) </OL> На підставі першої умови оптимальності потенціали знаходять з умов <IMG SRC=dopc70941.zip NAME=graphics468 ALIGN=BOTTOM WIDTH=63 HEIGHT=21 BORDER=0> і один, довільно обраний, потенціал прирівнюють до нуля, наприклад <IMG SRC=dopc70944.zip NAME=graphics469 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> . Якщо при перевірці другої умови оптимальності виявиться, що <IMG SRC=dopc70942.zip NAME=graphics470 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> для всіх незаповнених клітин, то опорний план оптимальний і відповідне значення цільової функції Z визначає мінімальні витрати. Якщо ж знайдеться хоча б одна клітина, для якої <IMG SRC=dopc70946.zip NAME=graphics471 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> , То план не оптимальний і можна перейти до нехудшему опорному плану. 3) Перехід до нехудшему опорному плану. Перехід до не гіршого опорному плану здійснюють за допомогою циклу перерозподілу вантажу. Цикл являє собою замкнуту ламану, ланки якої взаємно перпендикулярні і вершини циклу, крім однієї, знаходяться в заповнених клітках. Наведемо приклади різновидів форм циклів: У кожному випадку тільки одна вершина циклу перебуває у незаповненою клітці. Її називають початком циклу і визначають за найбільшою порушення умови оптимальності (6), тобто по максимальній оцінці <IMG SRC=dopc70947.zip NAME=graphics472 ALIGN=BOTTOM WIDTH=104 HEIGHT=21 BORDER=0> . Клітці початку циклу присвоюють знак «+», у всіх інших вершинах циклу знаки чергують «-», «+» і т.д. З клітин циклу зі знаками «-» вибирають ту, в якій знаходиться мінімальний вантаж. Це і буде та кількість вантажу, яке потрібно перерозподілити по циклу, тобто в клітці зі знаком «+» це кількість вантажу додається, а зі знаком «-» - віднімається. Клітини, які не задіяні в циклі, залишаються незмінними. Таким чином, отримуємо новий опорний план. Підраховуємо транспортні витрати, які повинні бути не більше попередніх. В іншому разі десь допущена помилка. Новий план знову перевіряємо на оптимальність, використовуючи умови (5) і (6). Якщо план оптимальний, то завдання виконане. Якщо ж план знову не оптимальний, то <a href="Працює" title="Працює">працюємо</a>, згідно з пунктом 3) до отримання оптимального плану і знаходження Z min. Транспортна задача відкритого типу Якщо для транспортної задачі виконується одна з умов <IMG SRC=dopc70948.zip NAME=graphics473 ALIGN=BOTTOM WIDTH=73 HEIGHT=43 BORDER=0> або <IMG SRC=dopc70949.zip NAME=graphics474 ALIGN=BOTTOM WIDTH=73 HEIGHT=43 BORDER=0> , то модель задачі називають відкритою. Щоб таке завдання мала рішення, необхідно її привести до закритого типу, тобто щоб виконувалася рівність <IMG SRC=dopc70950.zip NAME=graphics475 ALIGN=BOTTOM WIDTH=73 HEIGHT=43 BORDER=0> . Це роблять так: якщо <IMG SRC=dopc70948.zip NAME=graphics476 ALIGN=BOTTOM WIDTH=73 HEIGHT=43 BORDER=0> , То додають фіктивного споживача з попитом <IMG SRC=dopc70952.zip NAME=graphics477 ALIGN=BOTTOM WIDTH=99 HEIGHT=43 BORDER=0> (В розподільній таблиці з'явиться додатковий стовпець), якщо <IMG SRC=dopc70949.zip NAME=graphics478 ALIGN=BOTTOM WIDTH=73 HEIGHT=43 BORDER=0> , То додають фіктивного постачальника з пропозицією <IMG SRC=dopc70954.zip NAME=graphics479 ALIGN=BOTTOM WIDTH=100 HEIGHT=43 BORDER=0> (В розподільній таблиці з'явиться додатковий рядок). В обох випадках тарифи вважають рівними нулю. Далі завдання вирішується за таким же порядком, як було розглянуто раніше. Запишемо алгоритм розв'язання транспортної задачі: 1) Перевірка типу моделі ТЗ. 2) Побудова початкового опорного плану (будь-яким способом). 3) Перевірка плану на вирожденність. 4) Перевірка плану на оптимальність методом потенціалів: а) знаходження потенціалів із системи <IMG SRC=dopc70955.zip NAME=graphics480 ALIGN=BOTTOM WIDTH=71 HEIGHT=44 BORDER=0> (Для всіх заповнених клітин); б) перевірка другої умови оптимальності <IMG SRC=dopc70942.zip NAME=graphics481 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> (Для всіх порожніх клітин). 5) Перехід до нехудшему опорному плану (якщо це необхідно). Приклад. На складах є запаси однотипного товару в кількості а (35: 40; 40; 50), який необхідно доставити споживачам. Потреби споживачів задає вектор b (31; 52; 17; 20). Матриця витрат на доставку одиниці товару від i-го постачальника j-му споживачеві: з = <IMG SRC=dopc70957.zip NAME=graphics482 ALIGN=BOTTOM WIDTH=65 HEIGHT=81 BORDER=0> Скласти план перевезень з мінімальними <a href="Транспорт" title="Транспорт">транспортними</a> витратами. Рішення. Визначимо тип моделі транспортної задачі. Сумарна потужність постачальників: <IMG SRC=dopc70958.zip NAME=graphics483 ALIGN=BOTTOM WIDTH=43 HEIGHT=41 BORDER=0> 35 +40 +40 +50 = 165 (одиниць товару); Сумарний попит споживачів: <IMG SRC=dopc70959.zip NAME=graphics484 ALIGN=BOTTOM WIDTH=44 HEIGHT=43 BORDER=0> 31 +52 +17 +20 = 120 (одиниць товару). Оскільки <IMG SRC=dopc70960.zip NAME=graphics485 ALIGN=BOTTOM WIDTH=45 HEIGHT=41 BORDER=0><IMG SRC=dopc70961.zip NAME=graphics486 ALIGN=BOTTOM WIDTH=31 HEIGHT=41 BORDER=0> , То маємо модель відкритого типу. Введемо фіктивного споживача, попит якого дорівнює <IMG SRC=dopc70962.zip NAME=graphics487 ALIGN=BOTTOM WIDTH=27 HEIGHT=20 BORDER=0><IMG SRC=dopc70963.zip NAME=graphics488 ALIGN=BOTTOM WIDTH=41 HEIGHT=41 BORDER=0><IMG SRC=dopc70959.zip NAME=graphics489 ALIGN=BOTTOM WIDTH=44 HEIGHT=43 BORDER=0> 165 -120 = 45 (одиниць товару). Тарифи <IMG SRC=dopc70965.zip NAME=graphics490 ALIGN=BOTTOM WIDTH=29 HEIGHT=20 BORDER=0> 0. Т.ч. отримуємо модель закритого типу, m = 4 - число постачальників, n = 5 - число споживачів. Ранг матриці завдання <IMG SRC=dopc70966.zip NAME=graphics491 ALIGN=BOTTOM WIDTH=143 HEIGHT=16 BORDER=0> . Побудуємо початковий опорний план методом мінімального елемента (найменшої вартості). <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=64><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=65><COL WIDTH=1><COL WIDTH=56><COL WIDTH=89><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=25> <IMG SRC=dopc70914.zip NAME=graphics492 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> <IMG SRC=dopc70928.zip NAME=graphics493 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TABLE></CENTER></LI></LI></LI><CENTER><TABLE><TR><TD></TD><TD COLSPAN=2 WIDTH=72> 31 </TD><TD COLSPAN=2 WIDTH=72> 52 </TD><TD COLSPAN=2 WIDTH=72> 17 </TD><TD COLSPAN=2 WIDTH=81> 20 </TD><TD COLSPAN=2 WIDTH=72> 45 </TD><TD WIDTH=89> <IMG SRC=dopc70937.zip NAME=graphics494 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 35 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 4 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 1 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 0 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> 15 </TD><TD COLSPAN=2 WIDTH=81> 20 </TD><TD COLSPAN=2 WIDTH=72> </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 40 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 8 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> 31 </TD><TD COLSPAN=2 WIDTH=72> 9 </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 40 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 6 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 8 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 7 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 10 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 4 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> 40 </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 50 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 6 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 7 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 4 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> 43 </TD><TD COLSPAN=2 WIDTH=72> 2 </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> 5 </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=25> <IMG SRC=dopc70939.zip NAME=graphics495 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> </TD><TD COLSPAN=2 WIDTH=72> 1 </TD><TD COLSPAN=2 WIDTH=72> 2 </TD><TD COLSPAN=2 WIDTH=72> 3 </TD><TD COLSPAN=2 WIDTH=81> 1 </TD><TD COLSPAN=2 WIDTH=72> - 4 </TD><TD WIDTH=89> Таб.1 </TD></TR></TABLE></CENTER> Число заповнених клітин розподільчої таблиці 8 дорівнює рангу матриці завдання r = 8, отже, опорний план є невиродженим. Транспортні витрати,<a href="Відповідь" title="Відповідь"> відповідні</a> опорному плану: <IMG SRC=dopc70971.zip NAME=graphics496 ALIGN=BOTTOM WIDTH=333 HEIGHT=20 BORDER=0> (Ден. од.). Досліджуємо опорний план на оптимальність, використовуючи метод потенціалів. Доповнимо таблицю 1 стовпцем і рядком потенціалів <IMG SRC=dopc70972.zip NAME=graphics497 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> і <IMG SRC=dopc70973.zip NAME=graphics498 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> . Систему потенціалів знайдемо, використовуючи перша умова оптимальності: для заповнених поставками клітин <IMG SRC=dopc70974.zip NAME=graphics499 ALIGN=BOTTOM WIDTH=65 HEIGHT=21 BORDER=0> . <IMG SRC=dopc70944.zip NAME=graphics500 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70976.zip NAME=graphics501 ALIGN=BOTTOM WIDTH=59 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70977.zip NAME=graphics502 ALIGN=BOTTOM WIDTH=59 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70978.zip NAME=graphics503 ALIGN=BOTTOM WIDTH=60 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70979.zip NAME=graphics504 ALIGN=BOTTOM WIDTH=61 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70980.zip NAME=graphics505 ALIGN=BOTTOM WIDTH=61 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70981.zip NAME=graphics506 ALIGN=BOTTOM WIDTH=61 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70982.zip NAME=graphics507 ALIGN=BOTTOM WIDTH=61 HEIGHT=20 BORDER=0> ; <IMG SRC=dopc70983.zip NAME=graphics508 ALIGN=BOTTOM WIDTH=61 HEIGHT=20 BORDER=0> . З записаної системи знаходимо: <IMG SRC=dopc70944.zip NAME=graphics509 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70985.zip NAME=graphics510 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70986.zip NAME=graphics511 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70987.zip NAME=graphics512 ALIGN=BOTTOM WIDTH=39 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70988.zip NAME=graphics513 ALIGN=BOTTOM WIDTH=32 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70989.zip NAME=graphics514 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70990.zip NAME=graphics515 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70991.zip NAME=graphics516 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70992.zip NAME=graphics517 ALIGN=BOTTOM WIDTH=44 HEIGHT=20 BORDER=0> . Перевіримо виконання другої умови оптимальності. Для всіх порожніх клітин має виконуватись нерівність: <IMG SRC=dopc70942.zip NAME=graphics518 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> . (1; 1) <IMG SRC=dopc70994.zip NAME=graphics519 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 0 + 1 - 5 = -4 <IMG SRC=dopc70509.zip NAME=graphics520 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (1, 2) <IMG SRC=dopc70996.zip NAME=graphics521 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 0 + 2 - 4 = -2 <IMG SRC=dopc70509.zip NAME=graphics522 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (1; 5) <IMG SRC=dopc70998.zip NAME=graphics523 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 0 - 4 - 0 = -4 <IMG SRC=dopc70509.zip NAME=graphics524 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (2, 3) <IMG SRC=dopc71000.zip NAME=graphics525 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 1 + 3 - 5 = -1 <IMG SRC=dopc70509.zip NAME=graphics526 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (2, 4) <IMG SRC=dopc71002.zip NAME=graphics527 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 1 + 1 - 8 = -6 <IMG SRC=dopc70509.zip NAME=graphics528 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (2, 5) <IMG SRC=dopc71004.zip NAME=graphics529 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 1 - 4 - 0 = -4 <IMG SRC=dopc70509.zip NAME=graphics530 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (3; 1) <IMG SRC=dopc71006.zip NAME=graphics531 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 4 + 1 - 6 = -1 <IMG SRC=dopc70509.zip NAME=graphics532 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (3, 2) <IMG SRC=dopc71008.zip NAME=graphics533 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 4 + 2 - 8 = -2 <IMG SRC=dopc70509.zip NAME=graphics534 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (3; 3) <IMG SRC=dopc71010.zip NAME=graphics535 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 4 + 3 - 7 = 0 <IMG SRC=dopc70509.zip NAME=graphics536 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (3, 4) <IMG SRC=dopc71012.zip NAME=graphics537 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 4 + 1 - 10 = -5 <IMG SRC=dopc70509.zip NAME=graphics538 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (4; 1) <IMG SRC=dopc71014.zip NAME=graphics539 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 4 + 1 - 5 = 0 <IMG SRC=dopc70509.zip NAME=graphics540 ALIGN=BOTTOM WIDTH=12 HEIGHT=15 BORDER=0> 0; (4; 4) <IMG SRC=dopc71016.zip NAME=graphics541 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 4 + 1 - 2 = 3 <IMG SRC=dopc71017.zip NAME=graphics542 ALIGN=BOTTOM WIDTH=12 HEIGHT=12 BORDER=0> 0. Оскільки серед вільних клітин є такі, в яких друга умова оптимальності не виконується, то план не оптимальний. Здійснимо перехід до нехудшему опорному плану. Найбільш перспективна для заповнення клітина (4, 4), тому що їй відповідає найбільша позитивна оцінка <IMG SRC=dopc71018.zip NAME=graphics543 ALIGN=BOTTOM WIDTH=111 HEIGHT=20 BORDER=0> 4 + 1 - 2 = 3. Знайдемо цикл перерозподілу вантажу для цієї клітини. Обраної для заповнення клітці присвоюємо знак «+», далі знаки чергуємо. Серед вершин зі знаком «-» вибираємо найменшу поставку. <IMG SRC=dopc71019.zip NAME=graphics544 ALIGN=BOTTOM WIDTH=77 HEIGHT=20 BORDER=0> - Обсяг перепоставкі. Перерозподілимо поставки по циклу, тим самим перейдемо до нового опорного плану. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=64><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=65><COL WIDTH=1><COL WIDTH=56><COL WIDTH=89><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=25> <IMG SRC=dopc70914.zip NAME=graphics545 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> <IMG SRC=dopc70928.zip NAME=graphics546 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD COLSPAN=2 WIDTH=72> 31 </TD><TD COLSPAN=2 WIDTH=72> 52 </TD><TD COLSPAN=2 WIDTH=72> 17 </TD><TD COLSPAN=2 WIDTH=81> 20 </TD><TD COLSPAN=2 WIDTH=72> 45 </TD><TD WIDTH=89> <IMG SRC=dopc70937.zip NAME=graphics547 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 35 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 4 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 1 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 0 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> 17 </TD><TD COLSPAN=2 WIDTH=81> 18 </TD><TD COLSPAN=2 WIDTH=72> </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 40 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 8 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> - 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> 31 </TD><TD COLSPAN=2 WIDTH=72> 9 </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 40 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 6 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 8 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 7 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 10 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> 40 </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 50 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 6 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 7 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> 43 </TD></TR></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></TABLE></CENTER></TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> 2 </TD><TD COLSPAN=2 WIDTH=72> 5 </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=25> <IMG SRC=dopc70939.zip NAME=graphics548 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> </TD><TD COLSPAN=2 WIDTH=72> 4 </TD><TD COLSPAN=2 WIDTH=72> 5 </TD><TD COLSPAN=2 WIDTH=72> 3 </TD><TD COLSPAN=2 WIDTH=81> 1 </TD><TD COLSPAN=2 WIDTH=72> - 1 </TD><TD WIDTH=89> Таб.2 </TD></TR></TABLE></CENTER><IMG SRC=dopc71024.zip ALIGN=LEFT> Транспортні витрати, відповідні опорному плану: <IMG SRC=dopc71025.zip NAME=graphics549 ALIGN=BOTTOM WIDTH=333 HEIGHT=20 BORDER=0> (Ден. од.). Досліджуємо опорний план на оптимальність. Знайдемо значення потенціалів, використовуючи перша умова оптимальності. Для заповнених поставками клітин <IMG SRC=dopc70974.zip NAME=graphics550 ALIGN=BOTTOM WIDTH=65 HEIGHT=21 BORDER=0> . <IMG SRC=dopc70944.zip NAME=graphics551 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71028.zip NAME=graphics552 ALIGN=BOTTOM WIDTH=44 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71029.zip NAME=graphics553 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71030.zip NAME=graphics554 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71031.zip NAME=graphics555 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71032.zip NAME=graphics556 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70990.zip NAME=graphics557 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70991.zip NAME=graphics558 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71035.zip NAME=graphics559 ALIGN=BOTTOM WIDTH=43 HEIGHT=20 BORDER=0> . Перевіримо виконання другої умови оптимальності. Для всіх порожніх клітин має виконуватись нерівність: <IMG SRC=dopc70942.zip NAME=graphics560 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> . Випишемо клітини, в яких умова порушено: (1, 2) <IMG SRC=dopc70996.zip NAME=graphics561 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> 0 + 5 - 4 = 1 <IMG SRC=dopc71038.zip NAME=graphics562 ALIGN=BOTTOM WIDTH=13 HEIGHT=13 BORDER=0> 0. Здійснимо перехід до нехудшему опорному плану. Найбільш перспективна для заповнення клітина (1, 2), т. к. їй відповідає позитивна оцінка <IMG SRC=dopc71039.zip NAME=graphics563 ALIGN=BOTTOM WIDTH=33 HEIGHT=20 BORDER=0> 1. Знайдемо цикл перерозподілу вантажу для цієї клітини. <IMG SRC=dopc71040.zip NAME=graphics564 ALIGN=BOTTOM WIDTH=71 HEIGHT=20 BORDER=0> - Обсяг перепоставкі. Число заповнених клітин розподільчої таблиці 8 дорівнює рангу матриці завдання r = 8, отже, опорний план (таб. 3) є невиродженим. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=64><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=56><COL WIDTH=1><COL WIDTH=65><COL WIDTH=1><COL WIDTH=56><COL WIDTH=89><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=25> <IMG SRC=dopc70914.zip NAME=graphics565 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> <IMG SRC=dopc70928.zip NAME=graphics566 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD><TD COLSPAN=2 WIDTH=72> 31 </TD><TD COLSPAN=2 WIDTH=72> 52 </TD><TD COLSPAN=2 WIDTH=72> 17 </TD><TD COLSPAN=2 WIDTH=81> 20 </TD><TD COLSPAN=2 WIDTH=72> 45 </TD><TD WIDTH=89> <IMG SRC=dopc70937.zip NAME=graphics567 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 35 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 4 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 1 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 0 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> 18 </TD><TD COLSPAN=2 WIDTH=72> 17 </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 40 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 3 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 8 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> - 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> 31 </TD><TD COLSPAN=2 WIDTH=72> 9 </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 40 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 6 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 8 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 7 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 10 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> </TD><TD COLSPAN=2 WIDTH=72> 40 </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=1> 50 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 5 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 6 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 7 </TD><TD WIDTH=1> </TD><TD WIDTH=65> 2 </TD><TD WIDTH=1> </TD><TD WIDTH=56> 0 </TD><TD WIDTH=89> 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=9> </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=72> 25 </TD><TD COLSPAN=2 WIDTH=72> </TD><TD COLSPAN=2 WIDTH=81> 20 </COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL></COL><CENTER><TABLE><TR><TD></TD><TD COLSPAN=2 WIDTH=72> 5 </TD><TD WIDTH=89> </TD></TR><TR VALIGN=TOP><TD WIDTH=64 HEIGHT=25> <IMG SRC=dopc70939.zip NAME=graphics568 ALIGN=BOTTOM WIDTH=15 HEIGHT=21 BORDER=0> </TD><TD COLSPAN=2 WIDTH=72> 3 </TD><TD COLSPAN=2 WIDTH=72> 4 </TD><TD COLSPAN=2 WIDTH=72> 3 </TD><TD COLSPAN=2 WIDTH=81> 0 </TD><TD COLSPAN=2 WIDTH=72> - 2 </TD><TD WIDTH=89> Таб.3 </TD></TR></TABLE></CENTER> Транспортні витрати, відповідні опорному плану: <IMG SRC=dopc71045.zip NAME=graphics569 ALIGN=BOTTOM WIDTH=343 HEIGHT=20 BORDER=0> (Ден. од.). Досліджуємо опорний план на оптимальність. Знайдемо значення потенціалів, використовуючи перша умова оптимальності. Для заповнених поставками клітин <IMG SRC=dopc70941.zip NAME=graphics570 ALIGN=BOTTOM WIDTH=63 HEIGHT=21 BORDER=0> . <IMG SRC=dopc70944.zip NAME=graphics571 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71048.zip NAME=graphics572 ALIGN=BOTTOM WIDTH=44 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71049.zip NAME=graphics573 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71050.zip NAME=graphics574 ALIGN=BOTTOM WIDTH=39 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71051.zip NAME=graphics575 ALIGN=BOTTOM WIDTH=35 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71052.zip NAME=graphics576 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> , <IMG SRC=dopc70990.zip NAME=graphics577 ALIGN=BOTTOM WIDTH=36 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71054.zip NAME=graphics578 ALIGN=BOTTOM WIDTH=37 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71055.zip NAME=graphics579 ALIGN=BOTTOM WIDTH=44 HEIGHT=20 BORDER=0> . Перевіримо виконання другої умови оптимальності. Для всіх порожніх клітин має виконуватись нерівність: <IMG SRC=dopc70942.zip NAME=graphics580 ALIGN=BOTTOM WIDTH=111 HEIGHT=21 BORDER=0> . Друга умова оптимальності виконується для всіх вільних клітин, отже, план оптимальний. Найменші транспортні витрати <IMG SRC=dopc71057.zip NAME=graphics581 ALIGN=BOTTOM WIDTH=60 HEIGHT=20 BORDER=0> . Відповідь: <IMG SRC=dopc71057.zip NAME=graphics582 ALIGN=BOTTOM WIDTH=60 HEIGHT=20 BORDER=0> ; Оптимальний план розподілу поставок розташований у таб. 3. Завдання для самостійної роботи. Скласти план перевезень з мінімальними транспортними витратами. <CENTER><TABLE WIDTH=620 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=61><COL WIDTH=166><COL WIDTH=93><COL WIDTH=63><COL WIDTH=165><TR VALIGN=TOP><TD WIDTH=61> а) </TD><TD WIDTH=166> <IMG SRC=dopc71059.zip NAME=graphics583 ALIGN=BOTTOM WIDTH=104 HEIGHT=127 BORDER=0> </TD><TD WIDTH=93> </TD><TD WIDTH=63> б) </TD><TD WIDTH=165> <IMG SRC=dopc71060.zip NAME=graphics584 ALIGN=BOTTOM WIDTH=104 HEIGHT=127 BORDER=0> </TD></TR></TABLE></CENTER> Рішення оптимізаційних задач за допомогою Excel При вирішенні оптимізаційних економічних завдань необхідно пройти через такі етапи: <UL><LI> Скласти математичну модель економічної задачі; <LI> Вирішити отриману екстремальну математичну задачу; <LI> Дати економічну інтерпретацію відповіді. </UL> Розглянемо проходження цих етапів на прикладі задачі про використання ресурсів. Приклад. Для виготовлення виробів двох видів А і В на заводі використовують сировину чотирьох типів (І, ІІ, ІІІ, IV). Для випуску виробу А необхідно 2 одиниці сировини І типу; 1 од. сировини ІІ типу; 2 од. сировини І І І типу; 1 од. сировини IV типу. Для виготовлення виробу В потрібно 3 одиниці сировини І типу; 1 од. сировини ІІ типу; 1 од. сировини І І І типу. Запаси сировини становлять: І типу - 21 од., ІІ типу - 8 од., І І І типу - 12 од., IV типу - 5 од. Випуск одного виробу типу А приносить 3 грн. прибутку, а одного виробу типу В - 2 грн. прибутку. Скласти план виробництва, що забезпечує найбільший прибуток. Рішення. <UL><LI> Складання математичної моделі. </UL> Питання завдання, сформульований у вигляді «скласти план виробництва, що забезпечує найбільший прибуток», означає, що необхідно визначити, яку кількість виробів А і В потрібно виробляти (для досягнення найбільшого прибутку). Так як необхідно визначити кількість виробів А і В, то введемо такі позначення: <IMG SRC=dopc71061.zip NAME=graphics585 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> - Кількість виробів А, плановане до випуску; <IMG SRC=dopc71062.zip NAME=graphics586 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> - Кількість виробів В, плановане до випуску; Z (цільова функція задачі) за своїм економічним змістом - це прибуток. (Оскільки з умови завдання ми бачимо, що <a href="Слово" title="Слово">слово</a> «найбільша», пов'язане з екстремумів, відповідає прибутку). Отримаємо: <IMG SRC=dopc71063.zip NAME=graphics587 ALIGN=BOTTOM WIDTH=116 HEIGHT=124 BORDER=0> - Математична модель задачі. <UL><LI> Рішення отриманої екстремальної задачі: </UL> Для вирішення завдання скористаємося можливостями <a href="Microsoft_Excel" title="Microsoft Excel">Microsoft Excel</a>. <UL><UL><UL><LI> Відкрийте Microsoft <a href="Excel" title="Excel">Excel</a>. <LI> У комірки першого рядка (в даному випадку А1 і В1) введіть позначення наявних у задачі змінних <IMG SRC=dopc71061.zip NAME=graphics588 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> , <IMG SRC=dopc71062.zip NAME=graphics589 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> (<a href="Мова" title="Мова">Мова</a> і шрифт значення не мають, тому що позначення необхідні для <a href="Розуміння" title="Розуміння">розуміння</a> смислів відповідних їм чисел). </UL></UL></UL><UL><LI> У комірки другого рядка (в даному випадку А2 і В2), відповідні заповненим осередкам першої, введіть довільні значення змінних (для простоти візьмемо значення 1, хоча насправді це можуть бути будь-які числа). Тим самим ми присвоюємо <IMG SRC=dopc71061.zip NAME=graphics590 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> і <IMG SRC=dopc71062.zip NAME=graphics591 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> поки значення 1. </UL> У комірку А4 введіть позначення цільової функції Z =. <UL><LI> У комірку В4 введіть формулу обчислення цільової функції з математичної моделі задачі </UL> ( <IMG SRC=dopc71068.zip NAME=graphics592 ALIGN=BOTTOM WIDTH=84 HEIGHT=21 BORDER=0> ), Підставляючи замість <IMG SRC=dopc71061.zip NAME=graphics593 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> і <IMG SRC=dopc71062.zip NAME=graphics594 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> , Відповідні їм значення з осередків А2 і В2. (Згадайте, що введення формули починається зі знака =) Після натискання кнопки Enter на екрані <a href="Монітор" title="Монітор">монітора</a> повинна бути наступне. (Продумайте, як зміниться картинка, якщо ввести інші значення <IMG SRC=dopc71061.zip NAME=graphics595 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> і <IMG SRC=dopc71062.zip NAME=graphics596 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> , Наприклад, не 1, а 2. А тепер поекспериментуйте. Виправдався ваш прогноз?) У комірки А5 і В5 введіть відповідно слова: А5 - Обмеження, В5 - Права частина обмеження. <UL><LI> У осередок А6 введіть формулу обчислення лівій частині першого обмеження <IMG SRC=dopc71073.zip NAME=graphics597 ALIGN=BOTTOM WIDTH=60 HEIGHT=21 BORDER=0> , Підставляючи замість <IMG SRC=dopc71061.zip NAME=graphics598 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> і <IMG SRC=dopc71062.zip NAME=graphics599 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> , Відповідні їм значення з осередків А2 і В2. <LI> У комірку В6 введіть вільний член першого обмеження - 21. Після натискання кнопки Enter на екрані монітора повинна бути наступне. <LI> Аналогічно в клітинку А7 введіть формулу обчислення лівій частині другого обмеження <IMG SRC=dopc71076.zip NAME=graphics600 ALIGN=BOTTOM WIDTH=45 HEIGHT=21 BORDER=0> , А в В7 його вільний член - 8; в клітинку А8 введіть формулу обчислення лівої частини третього обмеження <IMG SRC=dopc71077.zip NAME=graphics601 ALIGN=BOTTOM WIDTH=53 HEIGHT=21 BORDER=0> , А в В8 його вільний член - 12; в клітинку А9 введіть формулу обчислення лівій частині четвертого обмеження <IMG SRC=dopc71061.zip NAME=graphics602 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> , А в В9 його вільний член - 5; </LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></UL></COL></COL></COL></COL></COL><UL><LI> Після натискання кнопки Enter на екрані монітора повинна бути наступне. </UL> Таким чином, ми ввели всі дані умови задачі у комп'ютер і підготувалися до того, щоб завдання вирішити. <UL><LI> У <a href="Меню" title="Меню">меню</a> Сервіс виберіть команду Пошук рішення (<a href="Саме" title="Саме">саме</a> вона є інструментом для пошуку рішень задач оптимізації) <LI> У цій команді вам буде запропоновано встановити цільову комірку. Саме слово «цільову» допоможе вам у подальшому згадати, про що йде мова. Звичайно ж, про значення цільової функції. Введіть це значення, клацнувши лівою кнопкою мишки на комірці В4 (містить в даному випадку числове значення цільової функції). Отримаєте: <LI> Оскільки в даній задачі функція Z досліджується на максимум, то залишаємо Рівної: • максимального значення. </UL> Якщо вирішуємо завдання на мінімум, то потрібно поставити мітку • перед словами мінімального значення. <UL><LI> Далі натисніть на стрілку, розташовану в правій частині простору осередку Змінюючи чарунки:, в результаті чого на екрані має з'явитися наступне </UL> В отримане <a href="Простір" title="Простір">простір</a> необхідно ввести діапазон змінюються в задачі змінних (тобто клітинки, що містять числові значення <IMG SRC=dopc71061.zip NAME=graphics603 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> і <IMG SRC=dopc71062.zip NAME=graphics604 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> , Тому що саме <IMG SRC=dopc71061.zip NAME=graphics605 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> і <IMG SRC=dopc71062.zip NAME=graphics606 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> можуть приймати різні числові значення, серед яких ми і намагаємося відшукати оптимальне рішення задачі). Тобто заповнена осередок повинна прийняти вигляд: <UL><LI> Після цього заповнюють простір осередку Обмеження: Для чого потрібно клацнути по кнопці Додати, в результаті чого на екрані з'явиться нове вікно: </UL> У Посилання на клітинку: введіть номер комірки, що містить ліву частину обмеження (у даному випадку для першого обмеження - це осередок А6). Виберіть знак обмеження відповідно до математичної моделлю з пропонованих варіантів (у даному випадку <=, т. к. перше обмеження зі знаком <IMG SRC=dopc71083.zip NAME=graphics607 ALIGN=BOTTOM WIDTH=13 HEIGHT=15 BORDER=0> ) У Обмеження: введіть номер комірки, що містить вільний член обмеження (у даному випадку для першого обмеження - це осередок В6). Т.ч. перед вами на екрані повинна бути наступна картинка: Це ви ввели тільки перше обмеження, а є ще й інші, тому натисніть кнопку Додати і аналогічним чином введіть друге, третє і четверте обмеження. <UL><LI> Але після того, як всі обмеження системи введені, ще рано натискати ОК, тому що в <a href="Математика" title="Математика">математичній</a> моделі є умова невід'ємності змінних ( <IMG SRC=dopc71084.zip NAME=graphics608 ALIGN=BOTTOM WIDTH=81 HEIGHT=21 BORDER=0> ), А в описі завдання для комп'ютера воно ще не згадувалося. </UL> Тому після введення останнього обмеження знову натисніть кнопку Додати і в Посилання на клітинку: введіть номер комірки, що містить числове значення <IMG SRC=dopc71061.zip NAME=graphics609 ALIGN=BOTTOM WIDTH=16 HEIGHT=21 BORDER=0> ; Виберіть знак> =; а в Обмеження: введіть 0. Ще раз натисніть Додати і аналогічним чином створіть умова позитивності для <IMG SRC=dopc71062.zip NAME=graphics610 ALIGN=BOTTOM WIDTH=17 HEIGHT=21 BORDER=0> . <UL><LI> Таким чином, комп'ютер отримав всі ті обмеження, які є в умові завдання, тому тепер можна натиснути ОК. У результаті на екрані з'явиться наступне: </UL> З'явилося? Якщо ТАК, то натискайте Виконати. І погодьтеся на те, щоб Зберегти знайдене рішення. Тобто у вікні натисніть ОК. <UL><LI> Зверніть увагу на те, які тепер значення приймають <IMG SRC=dopc71087.zip NAME=graphics611 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> , <IMG SRC=dopc71088.zip NAME=graphics612 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> і Z. </UL> <IMG SRC=dopc71087.zip NAME=graphics613 ALIGN=BOTTOM WIDTH=15 HEIGHT=20 BORDER=0> = 4; <IMG SRC=dopc71088.zip NAME=graphics614 ALIGN=BOTTOM WIDTH=16 HEIGHT=20 BORDER=0> = 4; Z = 20 - Це і є знайдене оптимальне рішення задачі ( <IMG SRC=dopc71091.zip NAME=graphics615 ALIGN=BOTTOM WIDTH=56 HEIGHT=20 BORDER=0> ) І відповідне екстремальне значення цільової <a href="Функції" title="Функції">функції </a>( <IMG SRC=dopc71092.zip NAME=graphics616 ALIGN=BOTTOM WIDTH=56 HEIGHT=20 BORDER=0> ). Математично задача вирішена. Залишилося дати економічну інтерпретацію отриманим. <UL><LI> Дамо економічну інтерпретацію відповіді. </UL> Для досягнення найбільшого прибутку 20 грн. необхідно виробляти 4 вироби А та 4 вироби В. Література <OL><LI> Вітлінській В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування. - К.: КНЕУ, 2001. <LI> Дослідження операцій в економіці / Під ред. проф. Н.Ш. Кремера. - М.: <a href="Банки" title="Банки">Банки</a> і <a href="Біржі" title="Біржі">біржі</a>, ЮНИТИ, 2000. <LI> Конюховскій П.В. Математичні методи <a href="Дослідження_операцій" title="Дослідження операцій">дослідження операцій</a> в економіці: навчальний посібник. - СПб. - <a href="Москва" title="Москва">Москва</a> - <a href="Харків" title="Харків">Харків</a> - Мінськ, 2005. <LI> Кулян В.Р. та ін <a href="Математичне_програмування" title="Математичне програмування">Математичне програмування</a>. - К.: МАУП, 2005. <LI> Таха, Хемді. Введення в <a href="Дослідження_операцій" title="Дослідження операцій">дослідження операцій</a>. - М.: Видавничий дім «Вільямс», 2001. </OL></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI></LI>
	</div>

Будь ласка, не зберігайте тестовий текст.
Ваш ip: 3.129.247.196 буде збережений.

категорії
за типом
за алфавітом
завантажені