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


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


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


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


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


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


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


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


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


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



Приклад 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. Етикет – (прикріплювати) установлений порядок поведінки в товаристві, певному оточенні, наприклад, придворний етикет, дипломатичний етикет.




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

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

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

  

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


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