• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Реалізація алгоритму СМ для ЗЛП з вільними змінними

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

Приклад 1.4. Знайти найбільше значення функції при обмеженнях

Розв’язок. Ввівши базисні змінні так, щоб

приходимо до наступної симплексної таблиці

	–x1	–x2
y1	–1	–2
y2	–2	–1	–4
y3	–1
y4	–1
y5		–1
f		–6
	­

Оскільки на х₁ і х₂ не накладені умови невід’ємності, то вони вважаються вільними і їх потрібно виключити. Для виключення змінної х₁ виберемо за розв’язуючий елемент (–1). Здійснивши один крок перетворень Жордана-Гаусса, дістанемо:

звідки: , а відповідний рядок виключаємо з таблиці:

	–у1	–x2
y2	–2	3	–6
y3	–1
y4	–1
y5		–9
f		–12

Виключивши вільну змінну х₂, отримуємо

Виписавши вираз для , відповідний рядок виключаємо з симплексної таблиці:

	–у1	–у2
y3	1	–1
y4		–2
y5	–2
f	–5		–21
	­

Оскільки всі вільні члени додатні, то розв’язок , , , , є опорним, але не оптимальним. Підставивши одержані значення в вирази для х₁ і х₂, матимемо , .

В -рядку вибираємо від’ємний елемент (–5), який визначає розв’язуючий стовпчик. Будемо збільшувати змінну . З того, що , випливає, що перший рядок є розв’язуючим, а 1 – розв’язуючий елемент. Виконавши один крок перетворень Жордана-Гаусса, дістанемо

	–у3	–у2
y1		–1
y4	–3	1
y5
f		–1
		­

Даний план не є оптимальним. Після проведення одного кроку перетворень Жордана–Гаусса приходимо до таблиці:

Отже, план – оптимальний. Підставляючи отримані значення в вирази для вільних змінних, дістанемо оптимальний план:

Контрольні запитання та задачі

1. В чому полягає властивість скінченності алгоритму СМ?

2. Що таке “явище зациклення”?

3. Для яких форм запису ЗЛП можна застосовувати алгоритм СМ?

4. Дайте відповіді на наступні запитання:

а) коли опорний план оптимальний?

б) в якому випадку від одного опорного плану можна перейти до іншого з більшим значенням цільової функції?

в) коли цільова функція необмежена на множині планів?

г) в якому випадку ЗЛП має нескінченну множину оптимальних планів?

5. Як визначаються змінні, які вводяться і виводяться з базису відповідно?

6. Який елемент називається розв’язуючим?

7. Сформулюйте алгоритм одного кроку перетворення Жордана-Гаусса.

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

9. Що роблять після того, коли всі вільні члени стали невід’ємними?

10. Якщо в системі обмежень є обмеження-рівняння, то чому рівна базисна змінна? З чого починається розв’язок ЗЛП в цьому випадку?

11. Сформулюйте алгоритм виключення 0-рядка.

12. Методом тотожних перетворень знайти найбільше значення функції при умові невід’ємності змінних:

а)	б)
в)	г)

13. Знайти з допомогою симплексних таблиць найбільше значення функції f при умові невід’ємності змінних .

а)	б)	в)
г)	д)	е)
є)	ж)	з)
и)	і)	ї)
й)	к)

Читайте також:

1. Адекватна реалізація принципів міжнародної економіки можлива лише в стабільному політичному середовищі.
2. Альтернативна реалізація із вільним вихідним кодом – сервер SAMBA
3. Блоки схеми алгоритму
4. Важливою складовою економічної політики 60-х рр. була реалізація програми “нових рубежів” президента Дж. Кенеді.
5. Визначення алгоритму
6. Визначення алгоритму
7. Виконавець алгоритму
8. Виконання програми - реалізація мови програмування
9. Виплати кредиту нерівними (змінними) сумами основного боргу
10. Вироблення та реалізація раціональних управлінських рішень.
11. Виробнича функція з двома змінними факторами
12. Виробнича функція з двома змінними факторами

Переглядів: 382