Звіт про проходження практики на кафедре економічної кібернетики Київського національного університету імені Тараса Шевченка

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

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

 

2. Розв’язування задач

                             

 

                                             

 
xi ≥ 0, i = 1,…,6                                                  
       

Кажуть , що задача ЛП має канонічну форму , якщо всі обмеження (крім умов невід'ємності змінних) мають вигляд рівностей , а всі вільні члени ненегативні . Так що ми маємо задачу в канонічній формі.

Ідея симплекс - методу полягає в наступному. Спочатку потрібно знайти деяку ( початкову) вершину багатогранника допустимих рішень ( початкова дозволене базисне рішення ) . Потім потрібно перевірити це рішення на оптимальність . Якщо воно оптимально , то рішення знайдено ; якщо ні, то перейти до іншої вершині багатогранника і знову перевірити на оптимальність . Зважаючи кінцівки вершин багатогранника (наслідок кінцівки обмежень задачі ЛП) за кінцеве число " кроків" ми знайдемо шукану точку мінімуму або максимуму . Треба зауважити , що при переході від однієї вершини до іншої значення цільової функції убуває ( в задачі на мінімум) або зростає ( в задачі на максимум).

Таким чином , ідея симплекс - методу грунтується на трьох властивостях задачі ЛП .

Рішення . Щоб знайти початкове дозволене базисне рішення , тобто щоб визначити базисні змінні , систему (5.6) потрібно привести до " діагональному " виду . Застосовуючи метод Гаусса ( метод послідовного виключення невідомих) ,:

 
Базисні змінні x2, x4, x5, x6, 

 x2=40, x4=20, x5=10, x6=30,. Змінні x1 і x3 є небазисними: x1=0, x3=0 .  
Початкове базисне рішення:  
x0 = (0,40,0,20,10,30)                                         
Для перевірки на оптимальність знайденого x0 треба з цільової функції вивести змінні  
f(x) = -7x1 – 14x3  +880                                    (5.10)  
За допомогою (5.8) –(5.10) складаємо початкову симплекс-таблицю:

 
        У нульовий рядок записані коефіцієнти із зворотним знаком відповідних змінних при цільової функції . Критерій оптимальності ( для задачі на пошук мінімуму) : дозволене базисне рішення (x0) оптимально , якщо в нульовий сходинці немає жодного строго позитивного числа (не рахуючи значення цільової функції. Це правило поширюється і на наступні ітерації (таблиці ) . Елементи нульової рядки будемо називати оцінками стовпців.

Так що початкова дозволене базисне рішення (5.9 ) неоптимально : 7 > 0 , 14 > 0.

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

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

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

У таблиці 1 ведучий стовпчик - третій стовпчик , і ведучий рядок - четверта рядок ( min { 40 / 1 , 30 / 1 } = 30 / 1 ) позначені стрілками , а ведучий елемент - кружечком . Провідний елемент показує , що базисну змінну x6 потрібно замінити на небазисной x3 . Тоді новими базисними змінними будуть x2 , x3 , x4 , x5 , , а небазисними - x1 , x6 , . Це й означає перехід до нової вершині багатогранника допустимих рішень . Щоб знайти значення координат нового допустимого базисного рішення x00 потрібно будувати нову симплекс - таблицю і провести в ній елементарні перетворення:

а ) всі елементи провідного рядка поділити на провідний елемент , перетворивши цим самим провідний елемент в 1 (для простоти викладок ) ;

б) за допомогою провідного елементу ( рівного 1 ) всі елементи ведучого стовпчика перетворити на нулі ( аналогічно методу виключення невідомих ) ;

У результаті в нульовому стовпці отримано значення нових базисних змінних x2 , x3 , x4 , x5 , (див. таблицю 2 ) - базисні компоненти нової вершини x00 ( небазисні компоненти x1 = 0 , x6 = 0 , ) .

 
Нове базисне рішення x00=(0,10,30,20,40,0) неоптимальне

 
         Допустиме базисне рішення x000=(10,0,30,10,50,0) и воно оптимальне, т.к. в нульвомй рядку не має додатніх значень. Тому  f(x000)=390 є мінімальним значенням функції. 

 
 
Відповідь x000=(10, 0, 30, 10, 50, 0) - точка мінімуму, f(x000)=390.

3. Підбиття підсумків роботи. Оцінка роботи студентів

 

 

2.4.2. Конспект семінарського  заняття №2

Виконання задач:

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

Розглянемо задачу лінійного програмування:

 

 

 
Отримаємо одиничну матрицю додаванням штучних змінних

лише в ті рівняння, які не розв’язані відносно базисних змінних.

Нехай штучну змінну введено у кожне рівняння:

 

 

 
область допустимих розв’язків задачі розширилась.

Задача з даною системою обмежень називається розширеноб, або М-задачею

Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві

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

Якого б малого значення не набувала відповідна коефіцієнту штучна змінна xn + i , значення цільової функції   буде від’ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні

Якщо в оптимальному плані розширеної задачі існує хоча б одне значення xn + i > 0, то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна.

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.

Теорема

Якщо в оптимальному плані   розширеної задачі штучні змінні   то план  є оптимальним планом початкової задачі.

 

Приклад

 

 

 
Застосовуючи для розв’язування поставленої задачі симплекс-метод, спочатку запишемо систему обмежень у канонічній формі:

 

 

Зауважимо, що нерівність типу «≥» перетворюємо у рівняння введенням у ліву частину обмеження додаткової змінної зі знаком «–». Система містить лише два одиничні вектори  та   , а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом +1 штучну змінну х8, якій від-повідатиме одиничний вектор 

Тепер можемо розглянути розширену задачу лінійного програмування:

 

 

 
На відміну від додаткових змінних штучна змінна х8 має в ці-льовій функції Z коефіцієнт +М (для задачі на min) або –М (для задачі на max), де М — досить велике додатне число. У розширеній задачі базисними змінними є х5, х6, х8, а решта змінних вільні. Початковий опорний план задачі такий

 

Складемо першу симплексну таблицю цієї задачі:

 

 
Розраховуючи оцінки першого опорного плану, дістаємо: Z0 = –9M; Z1 – с1 = –8; Z2 – с2 = –10, Z3 – с3 = –М і т. д. Отже, ми отримуємо оцінки двох видів: одні з них містять М, а інші є звичайними числами. Тому для зручності розділимо оцінковий рядок на два. У перший оцінковий рядок будемо записувати звичайні числа, а в другий — числа з коефіцієнтом М. Оцінки першого плану не задовольняють умову оптимальності, і тому він є неоптимальним. Виконуємо перехід до наступного опорно-го плану задачі. Після першої ітерації з базису виведена штучна змінна х8. Дальше розв’язування продовжуємо за алгоритмом симплексного методу.

Наступні кроки розв’язування задачі наведені у загальній таблиці:

 

Оптимальним планом задачі є вектор:

 

 

Підбиття підсумків роботи. Оцінка роботи студентів

 

III. Аналіз методів викладання, що застосовувалися під час  практики

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

Поняття методу навчання відображає:

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

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

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

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

Методи навчання за версією Л.Клінберга

1. Монологічні методи:

• розповідь;

• лекція;
• демонстрація.

2. Форми співпраці:

• індивідуальні;
• групові;
• фронтальні;
• колективні.

3. Діалогічні методи: бесіди.

Крім вищезазначених виділяють інформаційні та інформаційно-ілюстративні методи навчання.

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

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

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

1. Аналіз методів, що застосовувалися при поясненні тематичного матеріалу

Лекція у вищій школі — це відповідальне багатоаспектне педагогічне дійство. Воно є вершиною педагогічної майстерності педагога-науковця. Академічна лекція має нести в собі не лише інформаційний, змістовий потенціал, а й соціально-педагогічний. Останнє вимагає від викладача високої педагогічної культури і професійної майстерності.