Задача лінійного програмування та деякі методи їх розв’язування

Нажмите для полного просмотра!

Задача лінійного програмування та деякі методи їх розв’язування, слайд №2

Задача лінійного програмування та деякі методи їх розв’язування, слайд №3

Задача лінійного програмування та деякі методи їх розв’язування, слайд №4

Задача лінійного програмування та деякі методи їх розв’язування, слайд №5

Задача лінійного програмування та деякі методи їх розв’язування, слайд №6

Задача лінійного програмування та деякі методи їх розв’язування, слайд №7

Задача лінійного програмування та деякі методи їх розв’язування, слайд №8

Задача лінійного програмування та деякі методи їх розв’язування, слайд №9

Задача лінійного програмування та деякі методи їх розв’язування, слайд №10

Задача лінійного програмування та деякі методи їх розв’язування, слайд №11

Задача лінійного програмування та деякі методи їх розв’язування, слайд №12

Задача лінійного програмування та деякі методи їх розв’язування, слайд №13

Задача лінійного програмування та деякі методи їх розв’язування, слайд №14

Задача лінійного програмування та деякі методи їх розв’язування, слайд №15

Задача лінійного програмування та деякі методи їх розв’язування, слайд №16

Задача лінійного програмування та деякі методи їх розв’язування, слайд №17

Задача лінійного програмування та деякі методи їх розв’язування, слайд №18

Задача лінійного програмування та деякі методи їх розв’язування, слайд №19

Задача лінійного програмування та деякі методи їх розв’язування, слайд №20

Задача лінійного програмування та деякі методи їх розв’язування, слайд №21

Задача лінійного програмування та деякі методи їх розв’язування, слайд №22

Задача лінійного програмування та деякі методи їх розв’язування, слайд №23

Задача лінійного програмування та деякі методи їх розв’язування, слайд №24

Задача лінійного програмування та деякі методи їх розв’язування, слайд №25

Задача лінійного програмування та деякі методи їх розв’язування, слайд №26

Задача лінійного програмування та деякі методи їх розв’язування, слайд №27

Задача лінійного програмування та деякі методи їх розв’язування, слайд №28

Задача лінійного програмування та деякі методи їх розв’язування, слайд №29

Задача лінійного програмування та деякі методи їх розв’язування, слайд №30

Задача лінійного програмування та деякі методи їх розв’язування, слайд №31

Задача лінійного програмування та деякі методи їх розв’язування, слайд №32

Задача лінійного програмування та деякі методи їх розв’язування, слайд №33

Задача лінійного програмування та деякі методи їх розв’язування, слайд №34

Задача лінійного програмування та деякі методи їх розв’язування, слайд №35

Задача лінійного програмування та деякі методи їх розв’язування, слайд №36

Задача лінійного програмування та деякі методи їх розв’язування, слайд №37

Задача лінійного програмування та деякі методи їх розв’язування, слайд №38

Задача лінійного програмування та деякі методи їх розв’язування, слайд №39

Задача лінійного програмування та деякі методи їх розв’язування, слайд №40

Задача лінійного програмування та деякі методи їх розв’язування, слайд №41

Задача лінійного програмування та деякі методи їх розв’язування, слайд №42

Задача лінійного програмування та деякі методи їх розв’язування, слайд №43

Задача лінійного програмування та деякі методи їх розв’язування, слайд №44

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задача лінійного програмування та деякі методи їх розв’язування. Доклад-сообщение содержит 44 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дисципліна “Інформаційні технології аналізу систем” Лекція 8-9

Слайд 2

Описание слайда:

Загальна задача лiнiйного програмування та її подання в канонічній формі. Загальна задача лiнiйного програмування та її подання в канонічній формі. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі лінійного програмування. Властивості розв’язків задачі лінійного програмування. Геометричний метод розв’язування задачі лінійного програмування.

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

Введемо позначення: Введемо позначення:

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Слайд 21

Описание слайда:

Запишемо задачу (5) – (7) у матричному вигляді: Запишемо задачу (5) – (7) у матричному вигляді: (8) (9) (10)

Слайд 22

Описание слайда:

Теорема 1. Множина всіх планів задачі (8)–(10) – опукла. Теорема 1. Множина всіх планів задачі (8)–(10) – опукла. Опуклу множину планів задачі лінійного програмування позначимо через М. Зауважимо, що М може бути порожньою множиною, опуклим многогранником або необмеженою опуклою многогранною областю.

Слайд 23

Описание слайда:

Нехай лінійна функція задачі лінійного програмування обмежена знизу і зверху на множині планів. Нехай лінійна функція задачі лінійного програмування обмежена знизу і зверху на множині планів. Теорема 2. Лінійна функція задачі лінійного програмування (8) – (10) досягає мінімального (максимального) значення у крайній точці опуклої множини М планів задачі. Якщо лінійна функція набуває мінімального (максимального) значення більш ніж в одній крайній точці, то вона набуває цього ж значення в будь-якій точці, яка є опуклою комбінацією цих точок.

Слайд 24

Описание слайда:

Теорема 3 (критерій крайності точки опуклої множини планів). Для того щоб точка Х, яка містить m додатніх координат, була крайньою точкою множини планів М задачі лінійного програмування (8)-(10), необхідно і досить, щоб вектори , які відповідають додатним компонентам , утворювали лінійно незалежну систему. Теорема 3 (критерій крайності точки опуклої множини планів). Для того щоб точка Х, яка містить m додатніх координат, була крайньою точкою множини планів М задачі лінійного програмування (8)-(10), необхідно і досить, щоб вектори , які відповідають додатним компонентам , утворювали лінійно незалежну систему.

Слайд 25

Описание слайда:

Розглянемо двовимiрну задачу мiнiмiзацiї: Розглянемо двовимiрну задачу мiнiмiзацiї: (11) Лiнiєю (поверхнею) рiвня функцiї є множина точок

Слайд 26

Описание слайда:

Слайд 27

Описание слайда:

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

Слайд 31

Описание слайда:

Слайд 32

Описание слайда:

Розглянемо більш детально алгоритм розв'язування двовимірної задачi лiнiйного програмування виду: Розглянемо більш детально алгоритм розв'язування двовимірної задачi лiнiйного програмування виду: (12) (13)

Слайд 33

Описание слайда:

1. Побудувати прямi, рiвняння яких одержуються внаслiдок замiни в обмеженнях (13) знакiв нерiвностей на знаки рiвностей. 1. Побудувати прямi, рiвняння яких одержуються внаслiдок замiни в обмеженнях (13) знакiв нерiвностей на знаки рiвностей. 2. Знайти пiвплощини, якi визначаються кожним з обмежень-нерівностей задачi. 3. Знайти множину допустимих розв”язкiв задачі M, як перетин знайдених півплощин.

Слайд 34

Описание слайда:

4. Побудувати пряму (лінію рівня цільової функції), при цьому величина h підбирається так, щоб лінія рівня проходила через множину допустимих розв”язкiв М. Побудувати вектор . 4. Побудувати пряму (лінію рівня цільової функції), при цьому величина h підбирається так, щоб лінія рівня проходила через множину допустимих розв”язкiв М. Побудувати вектор . 5. Рухаючи пряму в напрямі вектора с при розв”язуванні задачі максимізації (або в зворотньому напрямі при розв”язанні задачі мінімізації), знайти точку (множину точок), де цiльова функцiя приймає максимальне (мiнiмальне) значення, або встановити необмеженiсть зверху (знизу) функцiї на допустимій множинi.

Слайд 35

Описание слайда:

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