Решение задачи размещения оборудования методом Гомори - Контрольная работа

Замещение одного объекта другим с целью получения информации о важнейших свойствах объекта-оригинала с помощью объекта-модели называется "моделированием". Таким образом, моделирование может быть определено как представление объекта моделью для получения информации об этом объекте путем проведения экспериментов с его моделью. Теория замещения одних объектов (оригиналов) другими объектами (моделями) и исследование свойств объектов на их моделях называется теорией моделирования. Модель (фр. modиle, от лат. modulus - «мера, аналог, образец») - некоторый материальный или мысленно представляемый объект или явление, являющийся упрощенной версией моделируемого объекта или явления (прототипа) и в достаточной степени повторяющий свойства, существенные для целей конкретного моделирования (опуская несущественные свойства, в которых он может отличаться от прототипа). Процесс создания модели называется моделированием.

Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.

Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).

5/2 - [5/2] = (1/4 - [1/4])x3 (-1/8 - [-1/8])S1 - S2, S2 і 0

1/2 = 1/4x3 7/8S1 - S2, S2 і 0 - второе ограничение Гомори

Это ограничение добавляем в последнюю симплексную таблицу.

Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.

Определяем вектор, вводимый в базис: Можно ввести либо x3, либо S1. Введем вектор S1. Ю соответствует дополнительному ограничению.

Таблица 5 Решение

C4 B4 X4 8 6 - - - - -

X1 X2 X3 X4 S1 S2 S3

6 8 - X2 X1 X4 5/2 13/4 1/2 - 1 - 1 - - 2/7 -3/14 4/7 - - 1 - - - -1/7 5/14 -9/7 - - -

- S1 4/7 - - 2/7 - 1 -8/7 - zj ?j 40 8 6 - - - 2 -

- - - - - 2 -

4/7 - - 2/7 - - 6/7 -1

Получаем новый оптимальный нецелочисленный план.

Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие переменной S1.

В полученном плане максимальную дробную часть имеет компонента х2, поэтому записываем дополнительное ограничение по первой строке.

4/7 = 2/7х3 6/7S2 - S3, S3і 0 - третье ограничение Гомори.

Определяем вектор, вводимый в базис: Это вектор x3.

Минимальное значение q = 2, что соответствует дополнительной строке.

После проведения очередных симплексных преобразований получили: Таблица 6 Решение

C5 B5 X5 8 6 - - - - -

X1 X2 X3 X4 S2 S3 S4

6 8 - - X2 X1 X4 X3 2 7/2 - 2 - 1 - - 1 - - - - - - 1 - - 1 - -1 1 -3 3 1 -3/4 2 -7/2 zj ?j 41 8 6 - - - 2 -

- - - - - 2 -

1/2 - - - - -1 1/4 -1

План Х5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке: 1/2 = 1/4S3 - S4, S4 і 0 - четвертое ограничение Гомори. Т.к. базисной компонентой может быть S3, определяем величину. . Минимальное значение получилось по 3 строке, а не по строке Гомори, следовательно, переходим к М-задаче: введем дополнительную переменную X5 в ограничение Гомори.

Таблица 7 Решение

C5 B5 X5 8 6 - - - - - -M

X1 X2 X3 X4 S2 S3 S4 X5

6 8 - - -M X2 X1 X4 X3 X5 2 7/2 - 2 1/2 - 1 - - - 1 - - - - - - - 1 - - - 1 - - -1 1 -3 3 - 1 -3/4 2 -7/2 1/4 - - - - -1 - - - - 1 zj ?j 40-M/2 8 6 - - 2 -M/4 M -M

- - - - 2 -M/4 M -

Таблица 8 Решение

C6 B6 X6 8 6 - - - - - -M

X1 X2 X3 X4 S2 S3 S4 X5

6 8 X1 X2 2 7/2 - 1 1 - - - -1/2 3/8 Ѕ -1/8 - - - - - -

- S3 - - - - 1/2 -3/2 1 - -

- -M X3 X4 2 1/2 - - - - 1 - 7/4 -1/8 -9/4 3/8 - - - -1 - 1 zj ?j 40-M/2 8 6 - M/8 2-3M/8 - M M

- - - M/8 2-3M/8 - M -

Таблица 9 Решение

C7 B7 X7 8 6 - - - - -M

X1 X2 X3 X4 S2 S4 S5

6 8 X2 X1 X3 - - - 4/3 -1/3 -6 - - -

- S2 1 -8/3 - zj ?j 112/3 8 6 - 2/3 - 16/3 -

- - - 2/3 - 16/3 -

2/3 - - - 1/3 - 2/3 -1

Дробная часть = max(1/3; 2/3) = 2/3 Ю дополнительное ограничение записываем по второй строке.

2/3 = 1/3х4 2/3S4 - S5 ,S5і 0 - пятое ограничение Гомори.

Вектор, вводимый в базис: вводим х4.

Ю соответствует строке Гомори.

Таблица 10 Решение

C8 B8 X8 8 6 - - - -

X1 X2 X3 X4 S4 X5

6 8 - - X2 X1 X3 X4 2 3 3 2 - 1 - - 1 - - - - - 1 - - - - 1 2 -1 -8 2 -1 1 1 3 -3 zj ?j 36 8 6 - - 4 2

- - - - 4 2

План Х8 = (3; 2; 3; 2) - оптимальный целочисленный. Lmax = 36.

Экономическая интерпретация: согласно полученному решению предприятию необходимо закупить 3 машины типа "А" и 2 машины типа "В". При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

Геометрическая интерпретация метода Гомори: строим множество планов (см. рисунок). В точке 1 - оптимальный нецелочисленный план.

Рисунок 2 Геометрическая интерпретация метода Гомори

Первое ограничение Гомори: 2/9x3 8/9x4 - S1 = 4/9, S1 і 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2

Из второго ограничения задачи: х4 = 16 - 4х1 - х2

Подставляем х3 и х4 в первое ограничение Гомори и после преобразований получаем: 4х1 2х2 S1 = 18, S1 і 0.

Отсюда имеем: 4х1 2х2 Ј 18. Это ограничение отсекает от множества планов область, содержащую точку 1. Новый оптимальный нецелочисленный план - точка 2.

Второе ограничение Гомори : 1/4x3 7/8S1 - S2 = 1/2, S2 і 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2

Из первого ограничения Гомори: S1 = 18 - 4х1 - 2х2

Получаем: 4х1 3х2 S2 = 20, S2 і 0 или 4х1 3х2 Ј 20. Это ограничение отсекает от множества планов область, содержащую точку 2. Новый оптимальный нецелочисленный план - точка 3.

Третье ограничение Гомори : 2/7x3 6/7S2 - S3 = 4/7, S3 і 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2

Из второго ограничения Гомори: S2 = 20 - 4х1 - 3х2

После подстановки x3 и S2 в третье ограничение Гомори получаем: 4х1 4х2 Ј 22. Это ограничение отсекает от множества планов область, содержащую точку 3. Новый оптимальный нецелочисленный план - точка 4.

Четвертое ограничение Гомори : 1/4S3 - S4 = 1/2, S4 і 0

Из третьего ограничения Гомори: S3 = 22 - 4х1 - 4х2

Получаем: х1 х2 S4 = 5, S4 і 0. Отсюда имеем: х1 х2 Ј 5. Это ограничение отсекает от множества планов область, содержащую точку 4. Новый оптимальный нецелочисленный план - точка 5.

Пятое ограничение Гомори : 1/3x4 2/3S4 - S5 = 2/3, S5 і 0

Из второго ограничения задачи: х4 = 16 - 4х1 - х2

Из четвертого ограничения Гомори: S4 = 5 - х1 - х2

Получаем: 2х1 х2 S5 = 8, S5 і 0. Отсюда: 2х1 х2 Ј 8. Это ограничение отсекает от множества планов область, содержащую точку 5. Оптимальный целочисленный план - точка 6 с координатами (3;2).

Заштрихованная часть - целочисленное множество планов.

Размещено на .ru