Симплексный метод исследования и моделирования операций

Симплексный метод, большим достоинством которого является его простота, является очень практичным методом, поскольку он работает только с коэффициентами целевой функции и ограничениями.

Мы проиллюстрируем его работу на примере, но ранее мы покажем правила принятия решения для определения входящей переменной, той, которая уходит, большого M и того, как определить, что мы находимся в оптимуме; Все эти решающие правила были выведены из алгебраического метода, только здесь они были скомпонованы для использования в том типе симплексной платы, которая будет использоваться.

симплекс-метод-научно-моделирования и-операции-1

ВИДЫ ОГРАНИЧЕНИЙ

ограничения

Добавляется резервная переменная со стоимостью (или прибылью) в целевой функции, равной 0.

EJM:

2X1 - 4X2 <= 1, остается:

2X1 - 4X2 + X3 = 1 Cj числа X3 в целевой функции будет равно 0.

Ограничения ³

Избыточная переменная вычитается со стоимостью (или прибылью) в целевой функции, равной 0, и добавляется искусственная переменная со стоимостью + M или –M в зависимости от того, является ли она максимизацией или минимизацией.

EJM:

2X1 + 3X2> = 1, остается:

2X1 + 3X2 - X3 + X4 = 1 Cj элемента X3 в целевой функции будет 0. и Cj элемента X4 (искусственный) равно ± M

Ограничения =

Искусственная переменная с затратами + M или –M добавляется в зависимости от того, максимизация это или минимизация.

EJM:

2X1 + 3X2 = 8, остается:

2X1 + 3X2 + X3 = 8 Cj числа X3 в целевой функции будет ± M

Кроме того, необходимо принять во внимание следующие примечания:

Если в симплексной доске оптимального решения есть хотя бы одна избыточная или искусственная переменная в базовых переменных со значением> 0, проблема не имеет решения, это означает, что существует как минимум два исключительных ограничения, поэтому Не существует области возможного решения и, тем более, решения, в этом случае следует пересмотреть формулировку проблемы. Если при выборе выходящей переменной ни одна из основных переменных не ограничивает рост неосновной переменной, выбранной для ввода, проблема имеет неопределенное решение, и формулировка должна быть пересмотрена в поисках нового ограничения, которое не было учтено в первоначальной формулировке. Если в симплексной доске оптимума хотя бы одна из неосновных переменных имеет нулевой коэффициент (0) в функции цель, это ваш Zj - Cj = 0,у проблемы есть несколько решений, и одно из них предлагается нам.

Пример 1

Xi - количество продукта i, которое должно быть произведено.

Максимальное увеличение Z = X1 + X2 {Общий прирост подошв}

5X1 + 3X2 <= 15 {Доступные часы в зависимости от К}

3X1 + 5X2 <= 15 {Доступные часы в зависимости от B}

Xj> = 0; j = 1, 2

Задачи максимизации со всеми их ограничениями <= и с условием неотрицательности называются стандартной формой или нормальной формой.

Здесь мы должны достичь возможного базового решения, используя резерв и / или искусственные переменные, оставив систему уравнений такой:

Увеличить Z = X1 + X2

5X1 + 3X2 + X3 = 15

3X1 + 5X2 + X4 = 15

Xj> = 0; j = 1,2,3,4

Основные переменные - это те, коэффициенты которых образуют единичную матрицу.

В этом хаосе случайно оказываются слабые переменные X3 и X4.

Значение целевой функции Z находится перед квадратом Zj - Cj, в этом случае оно равно нулю (0) и рассчитывается путем умножения вектора-строки (в таблице это столбец непосредственно перед столбцом основных переменных VB.), который содержит коэффициенты основных переменных в исходной целевой функции вектор-столбцом независимых термов b

CX _B = Векторная строка коэффициентов исходной целевой функции текущих основных переменных, их значения находятся в первом столбце доски.

b = Вектор-столбец независимых членов ограничений, которые в то же время являются значениями текущих базовых переменных, их значения находятся под столбцом с именем b

CX _B = (0,0); b = (15,15) ' Z = CX _B * b = (0) (15) + (0) (15) = 0

Значение Zj - Cj вычисляется путем умножения вектора-строки CX _B на вектор-указатель aj столбца j-й переменной за вычетом Cj, то есть:

Zj - Cj = CX _B. aj - Cj;

Расчеты производятся следующим образом:

Z1 - C1 = CX _B a1 - C1 = (0,0). (5,3) '- 1 = (0) (5) + (0) (3) - 1 = -1

Z2 - C2 = CX _B a2 - C2 = (0,0). (3,5) '- 1 = (0) (3) + (0) (5) - 1 = -1

Z3 - C3 = CX _B a3 - C3 = (0,0). (1,0) '- 0 = (0) (1) + (0) (0) - 0 = 0

Z4 - C4 = CX _B a4 - C4 = (0,0). (0,1) '- 0 = (0) (0) + (0) (1) - 0 = 0

Выходная и входящая переменные перечислены ниже:

Cj	один	один	0	0	б / а а> 0
	VB	б	X1	X2	X3	Х4
0	X3	15	5	3	один	0	15/5 = 3
0	Х4	15	3	5	0	один	15/3 = 5
Zj - Cj	0	-один	-один	0	0

Переменный вход X1

Регулируемый выход X3

Переменная с самым отрицательным Zj-Cj - это либо X1, либо X2. X1 выбирается случайным образом.

В этой итерации b / a дает: 15/5 = 3 и 15/3 = 5;

Это означает, что базовая переменная X3 ограничивает рост входной переменной X1 до 3 (не позволяет ей принимать значения выше 3), а базовая переменная X4 ограничивает рост входной переменной X1 до 5 (не позволяет принимать значения выше 5).

Конечно, основная переменная, которая больше всего ограничивает рост входной переменной X1, - это X3, следовательно, это основная переменная, выбранная для выхода.

Строка базовой переменной, выбранной для выхода, делится на элемент, который находится на пересечении указанной строки со столбцом входной переменной, результирующая строка является основной строкой и помещается на новую доску, с которой кратные строки сводной таблицы добавляются к другим строкам предыдущей доски таким образом, что переменная, выбранная для ввода, удаляется из каждой из них, в нашем случае X1, эта процедура вызывается, сделайте единицу (1) на пересечении и остальные нули столбца (0), поэтому единичный вектор появится в указанном столбце, процедура повторяется на каждой итерации, пока все Zj - Cj не станут больше или равны нулю в случае максимизации или меньше или равным нулю в случае минимизации.

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

Обратите внимание, что к целевой функции добавляются несколько ограничений, чтобы исключить из нее основные переменные.

Cj	один	один	0	0	б / а а> 0
	VB	б	X1	X2	X3	Х4
один	X1	3	один	3/5	1/5	0	5
0	Х4	6	0	16/5	-3/5	один	8/15
Zj - Cj	3	0	-2/5	1/5	0

Переменный вход X2

Регулируемый выход X4

Cj	один	один	0	0	б / а а> 0
	VB	б	X1	X2	X3	Х4
один	X1	8/15	один	0	5/16	0
один	X2	8/15	0	один	-3/16	5/16
Zj - Cj	15/4	0	0	1/8	1/8

Оптимальное решение:

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

Решение уникальное: X1 * = 15/8; X2 * = 15/8; Z * = 14/4

Пример 2

Минимизировать Z = 6X1 + 4X2 + 2X3

6X1 + 2X2 + 6X3> = 6

6X1 + 4X2 = 12

2X1 - 2X2 <= 2

Xj> = 0; j = 1, 2, 3

Свернуть Z = 6X1 + 4X2 + 2X3 + MX5 + MX6

6X1 + 2X2 + 6X3 - X4 + X5 = 6

6X1 + 4X2 + X6 = 12

2X1 - 2X2 + X7 = 2

Xj> = 0; j = 1, 2, 3, 4, 5, 6, 7

Основные переменные: X5 = 6, X6 = 12, X7 = 2.

Оптимальное решение:

Переменные решения:

X1 = 0, X2 = 3, X3 = 0, Z = 12

Переменные Slack: X4 = 0, X7 = 8

Искусственные переменные: X5 = 0, X6 = 0

ПРОРЫВ ПОСТ-ОПТИМАЛЬНОГО АНАЛИЗА

Максимальное увеличение Z = X1 + X2 {Общий прирост подошв}

5X1 + 3X2 <= 15 {Доступные часы в зависимости от К}

3X1 + 5X2 <= 15 {Доступные часы в зависимости от B}

Xj> = 0; j = 1, 2

Оптимальная доска:

Cj	один	один	0	0	б / а а> 0
	VB	б	X1	X2	X3	Х4
один	X1	8/15	один	0	5/16	0
один	X2	8/15	0	один	-3/16	5/16
Zj - Cj	15/4	0	0	1/8	1/8

Оптимальное решение:

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

Сниженная стоимость:

Единицы = (денежная единица) / (единица продукта) = (мкм) / (вверх) = те же единицы, что и Cj

Двойная цена:

Единицы = (денежная единица) / (единица ресурса) = (мкм) / (ур)

Интерпретация сниженной стоимости:

В каком количестве денежных единиц целевая функция ухудшается при производстве единицы продукта, который не производится.

В минимизации: (Dz / Dx) В максимуме: (Ñz / Dx)

Если переменная базовая, уменьшенная стоимость равна 0. Если переменная не базовая, она> = 0. Когда она равна 0, это означает альтернативные решения.

Интерпретация двойной цены:

В том, сколько денежных единиц будет изменяться целевая функция, варьируя ограничивающую единицу ресурса.

Когда он> 0: (Dz / Db) или (Ñz / Ñb)

Когда он <0: (Dz / Ñb) или (Ñz / Db)

Ограничение ограничение, когда он ограничивает целевую функцию. Это происходит, когда выполняется равенство ограничения.

Если ограничение не является ограничивающим, двойная цена равна 0.

Если ограничение является ограничивающим, оно может принимать любое положительное, отрицательное или нулевое значение.

РАЗДЕЛЕННЫЕ ЖИВОТНЫЕ

Компания «Чучела животных» производит чучела голубей и ястребов. В текущих рыночных условиях вы можете продавать ястребов и голубей с прибылью в 20 долларов и 12 долларов соответственно.

Шкуры ястребов более жесткие и требуют больше времени для обработки, чем шкуры голубей. Меховая машина может обрабатывать 4 шкуры ястреба в минуту или 8 шкур голубей, используя ту же производительность. Линия розлива может наполнять 5 ястребов или 4 голубей в минуту. Ястребы идут на заключительную операцию на станке для заточки клюва производительностью 3,5 ястреба в минуту, рабочий день в отделении составляет 8 часов.

Сформулируйте модель линейного программирования, которая решает случай. Сформулируйте двойную задачу модели, сформулированной в (а). Решите модель и выполните административную интерпретацию решения. Определите оптимальное решение двойной задачи, прочитав его непосредственно из оптимальной таблицы. найдено в вопросе c.

Если не указано иное, следующие вопросы не зависят друг от друга и основаны на исходной постановке проблемы.

Есть возможность работать сверхурочно на кожевенной машине, на линии наполнения и на заточной машине. Какова наибольшая прибыль, получаемая за каждую сверхурочную работу в каждом из участков? Менеджер компании посещает очередь ястребов и голубей и замечает, что в некоторых процессах есть свободные мощности. Он решил распорядиться, чтобы все центры процесса использовались со всей установленной мощностью. Что бы вы ему сказали? Что произойдет с оптимальным решением, если прибыль от каждого голубя упадет как /. 9.00 - Для более качественной отделки игрушек установлена линия лакировки; Лакокрасочная линия может заполнять 5 ястребов в минуту или 4 голубя одновременно, а также рабочий день 8 часов. Повлияет ли это на оптимальное решение ?; если да, найдите новое решение.

ТЕОРЕТИЧЕСКОЕ ПРИМЕЧАНИЕ:

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

МОДЕЛЬ:

X1 = количество голубей в день

X2 = количество ястребов, производимых в день

МАКС 12X1 + 20X2

ПРИ УСЛОВИИ

0,125X1 + 0,25X2 <= 480 меховая машина

0,25X1 + 0,2X2 <= 480 линия заполнения

0,2857143X2 <= 480 пик резкости

КОНЕЦ

ОПТИМАЛЬНЫЙ НД НАЙДЕН НА ШАГЕ 2

ОБЪЕКТИВНАЯ ФУНКЦИЯ ЗНАЧЕНИЕ

1) 39680,00