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

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

Алгоритм СМ у формі тотожних перетворень

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

, (1.10)

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

(1.11)

при обмеженнях

(1.12)

(1.13)

Виразимо з (1.12) базисні змінні і перепишемо задачу (1.11) – (1.12) у вигляді 0-рівнянь.

(1.14)

На початку виробничої діяльності продукція не виготовляється, тому х₁= 0, х₂ = 0 і f = 0. Даний розв’язок є опорним. Як видно із (1.11), спочатку потрібно здійснювати випуск продукції х₂ (вартість виробу А₂ більша за вартість виробу А₁), тобто збільшувати х₂.

Стовпчик коефіцієнтів при х₂ в системі обмежень (1.14) будемо називати розв’язуючим, змінні у₁, у₂, у₃ – базисними змінними, а х₁ і х₂ – небазисними.

Оскільки ми збільшуємо х₂, то х₁=0 із (1.14), матимемо

Так як змінні , то

(1.15)

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

(1.16)

(1.17)

Покладаючи небазисні змінні , одержимо наступний опорний розв’язок: і .

Як видно з (1.17), наступне збільшення значення f можливе за рахунок збільшення змінної . Маємо Друге рівняння із (1.16) є розв’язуючим. З нього . Підставивши в (1.16) і (1.17), одержимо

(1.18)

(1.19)

Нехай y₁=0, y₂=0. Тоді і .

Як видно з (1.19), наступне збільшення f неможливе. Тому можна зробити наступний висновок: опорний розв’язок буде оптимальним, якщо у виразі в дужках для цільової функції (1.19) відсутні від’ємні коефіцієнти при небазисних змінних у₁ і у₂. Даний висновок за умови узагальнення може бути прийнятий за критерій оптимальності опорного розв’язку.

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

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

1. Rete-алгоритм
2. Алгоритм
3. Алгоритм
4. Алгоритм 1.
5. Алгоритм 2
6. Алгоритм RLE
7. Алгоритм безпосередньої заміни
8. Алгоритм Берлекемпа-Мессі
9. Алгоритм відшукання оптимального плану.
10. Алгоритм Гоморі
11. Алгоритм Дейкстри.
12. Алгоритм Деккера.

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