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

Решение задачи методом отсекающих плоскостей (метод Гомори)

Читайте также:
  1. I. Задачи и методы психологии народов.
  2. II. НАЗНАЧЕНИЕ, ОСНОВНЫЕ ЗАДАЧИ И ФУНКЦИИ ПОДРАЗДЕЛЕНИЯ
  3. II. Цели и задачи Конкурса
  4. II. Цели и задачи Лаборатории
  5. II. Цели и задачи службы .
  6. II. Цель и задачи Фестиваля
  7. III. Обучающие тестовые задачи.

Для решения целочисленной задачи воспользуется решением линейной задачи без требования целочисленности. Перепишем симплекс-таблицу решённой задачи из пункта 1.3.

Таблица 2.1

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5         -5     -2  
X1 9/2       -1   -1/2    
X2 7/4       -2   1/4 -1 1/2
X3 5/4       -1   -1/4   1/2
Y -16                

 

На основе этой симплекс-таблицы для базисной переменной x1 (у нее наибольшая дробная часть) строим уравнение отсекающей плоскости по следующей формуле:

где f – дробная часть свободного члена;

fij – дробные части коэффициентов строки.

Представим новое ограничение в форме Куна-Таккера:

x9=-1/2-(-5/16*x3-7/8*x5-5/8*x7-13/16*x8)

Добавляем это ограничение к условиям оптимального решения и решаем новую расширенную задачу симплекс-методом.

Таблица 2.2

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X4 7/2     -3/4   1/2   1/2 -3/4  
X6 229/8     21/16   23/8   29/8 -99/16  
X2 5/8     13/16   -1/8   -3/8 5/16  
X1 35/8     11/16   1/8   3/8 -13/16  
X9 -5/8     -5/16   -7/8   -5/8 -13/16  
Y -109/8     139/16   9/8   11/8 3/16  

Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X9.

Таблица 2.3

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X4 53/13     -6/13   17/13   14/13   -12/13
X6 434/13     48/13   124/13   109/13   -99/13
X2 5/13     9/13   -6/13   -8/13   5/13
X1                   -1
X8 10/13     5/13   14/13   10/13   -16/13
Y -179/13     112/13   12/13   16/13   3/13

Решение оптимально. Так как переменная X8, подчиненная требованию целочисленности, и имеет дробное значение, то необходимо ввести дополнительное сечение относительно этой переменной:

x10=-10/13-(-5/13*x3-1/13*x5-10/13*x7-10/13*x9)

 

Таблица 2.4

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X4 53/13     -6/13   17/13   14/13   -12/13  
X6 434/13     48/13   124/13   109/13   -99/13  
X2 5/13     9/13   -6/13   -8/13   5/13  
X1                   -1  
X8 10/13     5/13   14/13   10/13   -16/13  
X10 -10/13     -5/13   -1/13   -10/13   -10/13  
Y -179/13     112/13   12/13   16/13   3/13  

Используем двойственный симплекс-метод. Вводим в базис X9, выводим из базиса X10.

Таблица 2.5

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X4           7/5         -6/5
X6       15/2   103/10         -99/10
X2       1/2   -1/2   -1     1/2
X1       3/2   11/10         -13/10
X8           6/5         -8/5
X9       1/2   1/10         -13/10
Y -182/13     17/2   9/10         3/10

Полученное решение удовлетворяет поставленным ограничениям и требованиям целочисленности. Решение является оптимальным.

 

Ответ: Y=-14, X=(6;0;0;5;0;41;0;2;1;0).

 


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


Читайте в этой же книге: Решение задачи 1.2 | Решение задачи методом ветвей и границ 2 страница | Решение задачи методом ветвей и границ 3 страница | Решение задачи методом отсекающих плоскостей (метод Гомори) | Решение задачи методом ветвей и границ | Определение вида квадратичной формы | Решение задачи методом Била | Решение задачи сепарабельным симплекс-методом | Переход от прямой задачи к двойственной | Интерфейс |
<== предыдущая страница | следующая страница ==>
Решение задачи 1.3| Решение задачи методом ветвей и границ 1 страница

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