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


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


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


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


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


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


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


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


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


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



Контакти
 


Тлумачний словник






Приклад 2.

Знайти мінімальне значення функції:

 

,

за умов:

.


Розв’язання:

Помножимо другу нерівність на (– 1) і введемо додаткові змінні.

 

Початковий базис: вектори А4 та А5.

Псевдоплан: .

 

- тому виведемо вектор А5 і змінну х5.

Введемо – на основі розрахунку значення :

, = ввести вектор А1. Розв’язувальним елементом буде а21 (–1).

Оптимальний план початкової задачі:

,

та оптимальний план двоїстої задачі:

, .


3. Метод відтинаючих площин (метод Гоморі)

варіанти:

1. Перший алгоритм Гоморі для рішення повністю цілочисельних задач.

2. Другий алгоритм Гоморі для рішення частково цілочисельних задач.

Ідея розрахунків методом відтинаючих площин для розв’язання повністю цілочисельних задач (1-й метод Гоморі) полягає у такому підході:

1) лінійна задача (1)

(1)

Опорний план, який має канонічний вигляд:

(2)


2) якщо серед рівнянь-обмежень (2) є дробові значення базисних змінних xi = bi, то обирають серед них таке значення, яке має найбільшу дробову частину. Це рівняння

Перетворюють у додаткову нерівність:

(3)

Правила обрання чисел [aij] та [bi]:

1. Якщо дробові числа aij або bi є додатними числами, то [aij] та [bi] є цілими додатними числами і дорівнюють цілій частині числа aij або bi. Наприклад:

2. Якщо дрібне число aij або bi є від’ємним числом, то [aij] та [bi] є від’ємним цілим числом, яке за абсолютним значенням на “1” більше за абсолютне значення цілої частини числа aij або bi. Наприклад:

Якщо aij або bi є цілими числами, то αij =0, βi =0.

 

3. Додаткова нерівність (3) має лише додатні коефіцієнти. Вона множенням на «-1» спочатку приводиться до вигляду, який повинна мати нерівність у симплекс-методі згідно зі стандартною формою () , а потім за допомогою додаткової змінної перетворюється у рівняння , яке додається до оптимального опорного плану – системи (2) і разом із ним створює псевдоплан (має одне від’ємне значення ).

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

 

Ознакою відсутності розв’язку задачі є наявність у таблиці хоча б одного рядка з цілими величинами aij та вільним дробовим членом bi, що вказує на відсутність розв’язку в цілих числах (наприклад, ) .

 


Часткові цілочислові задачі (в них вимоги щодо цілочисельності ставляться лише до окремих змінних) розв’язуються так само, як попередні, за рахунок введення додаткового обмеження

,

де - визначається з відношень:

1) для нецілочислових значень змінних :

;

2) для цілочисельних значень змінних :

 

.

 



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

  1. Абсолютні синоніми (наприклад, власне мовні й запозичені) в одному тексті ділового стилю вживати не рекомендується.
  2. Алгоритм однофакторного дисперсійного аналізу за Фішером. Приклад
  3. Базові та прикладні класифікації
  4. В чому полягає явище тунелювання через потенціальний бар’єр, наведіть приклади.
  5. Визначення і приклади
  6. Врахування витраті втрат електроенергії. Приклад складання електробалансу.
  7. Головною метою наукової діяльності в системі вищої освіти повинен стати розвиток фундаментальних та приклад­них досліджень.
  8. Деякі приклади застосування ППП
  9. Дієслова з префіксом дис-виражають значення ліквідації дії, названої безпрефіксним дієсловом, наприклад: гармонізувати – дисгармонізувати, асоціювати – дисасоціювати.
  10. Для одиничного і дрібносерійного виробництва норма витрати визначається як укрупнена, наприклад, на 1000 станко-годин роботи даного виду роботи устаткування
  11. Додаток И - Приклад виконання ремонтного креслення деталі
  12. Етикет – (прикріплювати) установлений порядок поведінки в товаристві, певному оточенні, наприклад, придворний етикет, дипломатичний етикет.




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

<== попередня сторінка | наступна сторінка ==>
Двоїстий симплекс-метод | Приклад 3. Розв’язати лінійну задачу цілочислового програмування.

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

 

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


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