Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод «искусственного» базиса. М–задача линейного программирования

Читайте также:
  1. A. гностическим методам
  2. Amp;Сравнительная характеристика различных методов оценки стоимости
  3. C) Методы стимулирования поведения деятельности
  4. E) мировоззренческая, гносеологическая, методологическая.
  5. I ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
  6. I. Из истории развития методики развития речи
  7. I. ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ
  8. I. Определение эпидемического процесса и методологическое обоснование разделов учения об эпидемическом процессе.
  9. I. Определение эпидемического процесса и методологическое обоснование разделов учения об эпидемическом процессе.
  10. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

 

Рівні навчальних досягнень Бали Критерії оцінювання навчальних досягнень студентів
І. Початковий   Студент сприймає та відтворює тематичний матеріал з художньої культури на частковому рівні, однозначно його характеризує, демонструє недостатньо сформоване художнє мислення, елементарні навички та уміння у художньо-практичній діяльності.
    Студент володіє незначною частиною тематичного матеріалу з художньої культури, демонструє недостатньо сформований рівень сприймання мистецьких творів, виявляє певні творчі вміння інтерпретувати культурно – мистецькі явища, володіє незначною частиною спеціальної термінології; словниковий запас в основному дозволяє викласти думку на елементарному рівні.
    Студент здатний сприймати та інтерпретувати окремі художньо-культурні явища, знає незначну частину тематичного матеріалу, послуговуючись обмеженим термінологічним та словниковим запасом.
ІІ. Середній   Студент здатний сприймати та інтерпретувати культурно-мистецькі явища на репродуктивному рівні, не завжди розуміє художньо – образної сфери мистецьких творів; застосування знань та термінологічного запасу на практиці задовільне.
    Студент володіє знаннями та вміннями, які дають змогу інтерпретувати окремі культурно – мистецькі явища, недостатньо вміє сприймати, інтерпретувати мистецькі твори, які вимагають абстрактного мислення; виявляє недостатні знання спеціальної термінології; словниковий запас небагатий.
    Студент може сприймати та інтерпретувати значну частину тематичного матеріалу з художньої культури, але має недостатньо сформоване художнє мислення, не завжди послідовно та логічно характеризує окремі мистецькі твори, потребує уточнень і додаткових запитань; учень виявляє знання і розуміння основних тематичних положень, але не завжди вміє самостійно зробити аналіз культурно – мистецьких явищ, порівняння та висновки.
ІІІ. Достатній   Студент здатний сприймати та інтерпретувати художньо-культурні явища, не завжди робить переконливі висновки, не завжди послідовно викладає своє думки. Допускає термінологічні помилки; володіє основним програмно-тематичним матеріалом, але знання недостатньо стійкі; спостерігаються помітні позитивні зміни у художній діяльності учня.
    Студент уміє сприймати і відтворювати окремі художньо-культурні явища, досить повно характеризує художньо-образний зміст мистецьких творів, але демонструє стандартне мислення, бракує власних висновків, асоціацій, узагальнень, не завжди вміє поєднати своєрідність художніх образів та життєвих явищ; учень не завжди володіє спеціальною термінологією під час інтерпретації культурно-мистецьких явищ.
    Студент виявляє достатнє засвоєння тематичного матеріалу з художньої культури, але допускає несуттєві неточності у використанні спеціальної термінології, що потребують зауваження чи коригування, трапляються поодинокі недоліки в інтерпретації мистецьких творів і мовленнєвому оформленні власних роздумів щодо культурно - мистецьких явищ; не завжди самостійно може систематизувати та узагальнювати тематичний матеріал.
ІV. Високий   Студент має міцні інтегровані знання, виявляючи їх усвідомлення, але, аналізуючи художньо-культурні явища, допускає неточність формулювань та використання спеціальної термінології, не завжди обгрунтовано може довести власну думку щодо мистецьких творів, самостійно інтерпретувати їх зміст. Вказані неточності може виправляти самостійно.
    Студент володіє тематичним матеріалом з художньої культури у межах програми, вміє використовувати набуті знання, уміння і здібності у нових інтегрованих художньо-творчих завданнях, виявляє знання спеціальної термінології, їх усвідомлення та міцність, уміння систематизувати, узагальнювати, інтерпретувати культурно – мистецькі явища у їх взаємозв’язках, асоціювати їх з життєвими явищами.
    Студент має ґрунтовні, усвідомлені знання з художньої культури, здатний систематизувати, узагальнювати, сприймати та інтерпретувати інтегровані художньо – культурні явища на основі взаємодії різних видів мистецтв, широко застосовувати асоціативні зв’язки між художніми творами та життєвими явищами. Учень свідомо використовує спеціальну термінологію у роздумах, висновках та узагальненнях щодо художніх образів, пропонує нетипові, цікаві варіанти інтерпретації художньо-культурних явищ; рівень художньо –творчого мислення, світопізнання і світовідчуття високий; самостійно використовує набуті знання, вміння та здібності в художній діяльності.
       

Метод «искусственного» базиса. М–задача линейного программирования

(метод больших штрафов)

 

В этом методе ограничения изменяются введением искусственных переменных таким образом, чтобы экстремальная точка новой задачи находилась достаточно легко. Каждой искусственной переменной назначается большой положительный штраф М с тем, чтобы в оптимальном решении полученной задачи значение этой переменной было равно нулю.

Решим прямую задачу линейного программирования симплексным М-методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции

 

F(X) = 2x1+x2+3x3 при следующих условиях-ограничений (см. также M-задача).
x1+2x2+x3≤1000
3x1+5x2+2x3≤1500
x1≥100
x2≥100
x3≥200


Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

 

1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 = 200

 

Введем искусственные переменные x.
1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 0x9 + 1x10 + 0x11 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 + 0x9 + 0x10 + 1x11 = 200

 

Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x1+x2+3x3 - Mx9 - Mx10 - Mx11 => max

 

За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:

 

x9 = 100-x1+x6
x10 = 100-x2+x7
x11 = 200-x3+x8
которые подставим в целевую функцию:
F(X) = 2x1 + x2 + 3x3 - M(100-x1+x6) - M(100-x2+x7) - M(200-x3+x8) => max
или
F(X) = (2+1M)x1+(1+1M)x2+(3+1M)x3+(-1M)x6+(-1M)x7+(-1M)x8+(-400M) => max

 

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x9, x10, x11,

 

Переходим к основному алгоритму симплекс-метода.

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
0 x4 1000 1 2 1 1 0 0 0 0 0 0 0 1000
  x5 1500 3 5 2 0 1 0 0 0 0 0 0 750
  x9 100 1 0 0 0 0 -1 0 0 1 0 0 0
  x10 100 0 1 0 0 0 0 -1 0 0 1 0 0
  x11 200 0 0 1 0 0 0 0 -1 0 0 1 200
Индексная строка F(X1) -400M -2-1M -1-1M -3-1M 0 0 1M 1M 1M 0 0 0 0

Иногда такую таблицу представляют с дополнительной строкой для М.

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
  x4                        
  x5                        
  x9             -1          
  x10               -1        
  x11                 -1      
Индексная строка F(X0)   -2 -1 -3                
M   -400 -1 -1 -1                

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
1 x4 800 1 2 0 1 0 0 0 1 0 0 -1 800
  x5 1100 3 5 0 0 1 0 0 2 0 0 -2 366.67
  x9 100 1 0 0 0 0 -1 0 0 1 0 0 100
  x10 100 0 1 0 0 0 0 -1 0 0 1 0 0
  x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
Индексная строка F(X2) 600-200M -2-1M -1-1M 0 0 0 1M 1M -3 0 0 3+1M 0

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
  x4                   -1   -1  
  x5                   -3   -2  
  x1             -1            
  x10               -1          
  x3                 -1        
Индексная строка F(X3) 800-100M   -1-1M       -2 1M -3 2+1M   3+1M  

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
3 x4 500 0 0 0 1 0 1 2 1 -1 -2 -1 500
  x5 300 0 0 0 0 1 3 5 2 -3 -5 -2 150
  x1 100 1 0 0 0 0 -1 0 0 1 0 0 0
  x2 100 0 1 0 0 0 0 -1 0 0 1 0 0
  x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
Индексная строка F(X4) 900 0 0 0 0 0 -2 -1 -3 2+1M 1+1M 3+1M 0

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
4 x4 350 0 0 0 1 -0.5 -0.5 -0.5 0 0.5 0.5 0
  x8 150 0 0 0 0 0.5 1.5 2.5 1 -1.5 -2.5 -1
  x1 100 1 0 0 0 0 -1 0 0 1 0 0
  x2 100 0 1 0 0 0 0 -1 0 0 1 0
  x3 350 0 0 1 0 0.5 1.5 2.5 0 -1.5 -2.5 0
Индексная строка F(X5) 1350 0 0 0 0 1.5 2.5 6.5 0 -2.5+1M -6.5+1M 1M

 

Оптимальный план можно записать так:
x4 = 350
x8 = 150
x1 = 100
x2 = 100
x3 = 350
F(X) = 2*100 + 1*100 + 3*350 = 1350




Дата добавления: 2014-12-15; просмотров: 40 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Резервний час може використовуватися на тематичне оцінювання, регіональний компонент, узагальнення розділу (теми), відвідування виставок, музеїв тощо.| Южный филиал Национального университета

lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав