Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Задача цілочисельного програмування.

Читайте также:
  1. В чем основная задача самообразования
  2. В чём главная жизненная задача мужчины?
  3. Взаимосвязь технологической структуры с задачами организации и управления производством.
  4. Волшебная флейта перестройки: фильм «Город Зеро» как учебная задача
  5. Волшебная флейта перестройки: фильм «Город Зеро» как учебная задача.
  6. Вот уж поистине, главная задача ЦБ – сокращение населения России.
  7. ВСТРЕЧА ДВЕНАДЦАТАЯ. Задача и сверхзадача

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

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

 

 

Алгоритм методу Гоморі.

1. Розв’язуємо симплекс-методом ЗЛП без умови цілочисельності.

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

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

1) лінійне;

2) відсікає знайдений оптимальний нецілочисельний план;

3) не відсікає жодного цілочисельного плану.

Додаткове обмеження з вказаними особливостями називається правильним відсіканням. Розв’язуємо двоїстим симплекс-методом ЗЛП з додатковим обмеженням.

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

 

 

Побудова правильного відсікання.

 

Введемо такі позначення:

ціла частина числа , найбільше ціле число, яке не перевершує . Наприклад, , , .

дробова частина числа , , .

Наприклад, , , .

Відсікання Гоморі обирають наступним чином: серед нецілочисельних розв’язків системи обирають компоненту з максимальною дробовою частиною та з відповідного рівняння формують правильне відсікання

 

.

 

Вводимо нову змінну . Отримали розширену симплекс-таблицю, в якій в стовпці вільних членів є від’ємне число. Розв’язуємо цю задачу симплекс-методом. Якщо розв’язок не є цілочисельним, повторюємо алгоритм знову.

Приклад 10.

 

 

         
      1/3 5/3 17/3
           
–2     2/3 34/3 34/3

 

Розв’язок знайдений, але він не є цілочисельним. Максимальна дробова частина , будуємо додаткове відсікання за першою строкою.

 

,

 

обчислюємо дробові частини

 

,

,

.

 

Заносимо додаткове обмеження в таблицю і розв’язуємо двоїстим симплекс-методом.

 

         
1/3 5/3 17/3 1/3    
           
–1 –2 –2 –1    
2/3 34/3 34/3       10

 

Розв’язок є оптимальним і цілочисельним.

Відповідь: .

 

 


Дата добавления: 2015-08-05; просмотров: 62 | Нарушение авторских прав


Читайте в этой же книге: Задачі математичного і лінійного програмування | Математична модель задачі про використання сировини. | Геометричний метод розв’язування ЗЛП | Зведення ЗЛП до канонічної форми | Алгоритм однократного заміщення Жордана-Гауса | Симплексний метод | Отримання допустимого базисного розв’язку | Метод потенціалів. | Цикл перерахунку | ЗАВДАННЯ 2. |
<== предыдущая страница | следующая страница ==>
Двоїста задача| Транспортна задача.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)