Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Пряма та двоїста задачі лінійного проґрамування

Тема 1. Двоїстий та модифікований симплекс-метод. Блочні задачі ЛП

1. Пряма та двоїста задачі лінійного проґрамування.

2. Зв’язок між розв’язками прямої та двоїстої задач.

3. Отримання оптимального розв’язку двоїстої задачі за допомогою симплекс-методу.

4. Економічна інтерпретація задач лінійного проґрамування.

5. Двоїстий симплекс-метод.

6. Модифікований симплекс-метод.

7. Блочні задачі лінійного проґрамування. Метод Данціґа-Вулфа.

Пряма та двоїста задачі лінійного проґрамування

Для прямої задачі ЛП справедливі наступні співвідношення:

, .

Двоїста відносно прямої задача ЛП в канонічній формі має вигляд:

, .

Відповідно в матричній формі пряма задача зображається як

, а двоїста – , або .

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

Змінні прямої задачі

x₁	x₂	…	x_j	…	x_n
c₁	c₂	…	c_j	…	c_n
a₁₁	a₁₂	…	a_1j	…	a_1n	b₁	y₁
a₂₁	a₂₂	…	a_2j	…	a_2n	b₂	y₂
…	…	…	…	…	…	…	…
a_m1	a_m2	…	a_mj	…	a_mn	b_m	y_m

Змінні

двоїстої

задачі

Приклад.

Q= 5x₁+12x₂+4x₃à Max,

x₁+ 2x₂+ х₃< =10

2x₁ - x₂ + 3х₃ = 8

x₁ >=0, x₂ >=0, x₃ >=0.

Приводимо задачу до канонічної форми:

Q= 5x₁+12x₂+4x₃ +0x₄à Max,

x₁+ 2x₂+ х₃+ х₄ =10 à y₁

2x₁ - x₂ + 3х₃ +0x₄ = 8 à y₂

x₁ >=0, x₂ >=0, x₃ >=0, x₄ >=0

Умова двоїстої задачі:

G= 10y₁+ 8y₂à Min,

y₁+ 2y₂ > = 5

2y₁- y₂ > = 12

y₁+ 3y₂ > = 4

y₁+ 0y₂ > = 0,

y₁, y₂ >< 0.

Двоїста задача до двоїстої буде первісною прямою задачею, тобто, якщо A — пряма задача, D{A} — двоїста до A, то A=D{D{A}}. Покажемо, що це насправді так.

Тепер переходимо до двоїстої задачі:



<== попередня сторінка	\|	наступна сторінка ==>
Інтервали монотонності та точки екстремуму функцій.	\|	Зв’язок між розв’язками прямої та двоїстої задач

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.