Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

, (1.10)

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

(1.11)

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

(1.12)

(1.13)

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

(1.14)

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

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

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

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

(1.15)

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

(1.16)

(1.17)

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

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

(1.18)

(1.19)

Нехай y1=0, y2=0. Тоді і .

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

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

 


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

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




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

<== попередня сторінка | наступна сторінка ==>
Симплексний метод розв’язування ЗЛП (СМ) | Табличний запис ЗЛП. Алгоритм СМ для ЗЛП, представлених в симетричній формі.

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

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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