Правила построения новой симплекс-таблицы

Изменяют базисные переменные: меняют местами переменные из разрешающей строки и разрешающего столбца. Элементы из нижних клеток предыдущей симплекс-таблицы делят на верхний разрешающий элемент и записывают на соответствующие места в верхние клетки новой симплекс-таблицы.

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

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

Если в строке  есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода: Столбец с нулевым элементом в строке выбирается за разрешающий. Находят неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца. Из полученных отношений выбирают минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден. Затем выполняют еще один шаг симплекс-метода.

Если в столбце  есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода. При этом строка с нулевым элементом в столбце  выбирается за разрешающую.

Переходим к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₂, у₅, соответствующих разрешающему столбцу, а во второй столбец вводится пара переменных х₄, у₁, соответствующая разрешающей строке. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «3»:

	y баз	y 4	y 1	y 6
y св	x св x баз	- x1	- x 4	- x 3	bi
y 5	x 2	2/3	1/3	2/3	20/3
y2	x 5	10/3	-4/3	1/3	40/3
y 3	x 6	-2/3	-4/3	7/3	-8/3
cj		-8/3	20/3	-14/3	400/3

 

Решение ПЗЛП на втором шаге двойственного симплекс-метода также выписывается по строкам: = (0, 20/3, 0, 0, 40/3, -8/3),  = 400/3, решение ДЗЛП выписывается по столбцам: = (20/3, 0, 0, -8/3, 0, -14/3),  = 400/3. Данное решение также не оптимальное, поскольку в строке  еще остались отрицательные элементы. Необходимо продолжить поиск оптимального решения.

В строке  выбираем отрицательный элемент «-8/3». Над ним выбираем положительный, предпочтительнее «10/3», поскольку первая строка была выбрана на предыдущем шаге метода, следовательно, вторая строка – разрешающая (выделена жирным шрифтом):

 

	y баз	y 4	y 1	y 6
y св	x св x баз	- x1	- x 4	- x 3	bi
y 5	x 2	2/3	1/3	2/3	20/3
y2	x 5	«10/3»	-4/3	1/3	40/3
y 3	x 6	-2/3	-4/3	7/3	-8/3
cj		- 8/3	20/3	-14/3	400/3
					-

 

Находим максимальное отношение среди отношений элементов в строке целевой функции  к соответствующим элементам разрешающей строки

. Разрешающий столбец – первый, поскольку максимальное отношение соответствует ему.

Разрешающий элемент «10/3» находится на пересечении разрешающей строки и разрешающего столбца.

Заполнение нижних частей клеток осуществляется аналогично рассмотренному выше. Получаем следующую таблицу:

 

	y баз	y 4	y 1	y 6
y св	x св x баз	- x1	- x 4	- x 3	bi
y 5	x 2	2/3       -2/3	1/3       2	2/3        2	20/3          40/3
y2	x 5	«10/3»       1	-4/3    -4/3	1/3     1/3	40/3           40/3
y 3	x 6	-2/3     2/3	-4/3  -16/3	7/3        8	-8/3            0
cj		- 8/3     8/3	20/3   56/3	-14/3   44/3	400/3       1440/3

 

Переходим к следующей симплекс-таблице. При этом во вторую строку включается пара переменных х₁, у₄, соответствующих разрешающему столбцу, а в первый столбец вводится пара переменных х₅, у₂, соответствующая разрешающей строке. Клетки следующей таблицы заполняются элементами, полученными в результате деления соответствующих элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «10/3». Поскольку в нижних частях клеток таблицы все элементы положительные и разрешающий элемент также положительный, то в следующей таблице будет получено оптимальное решение и нет необходимости делить на две части клетки в последней таблице. Однако следует отметить, что в третьей строке в столбце b_i есть нулевой элемент. Это свидетельствует о том, что двойственная задача имеет альтернативные решения:

 

	y баз	y 2	y 1	y 6
y св	x св x баз	- x 5	- x 4	- x 3	bi
y 5	x 2	-1/5	3/5	3/5	4
y 4	x 1	3/10	-2/5	1/10	4
y 3	x 6	1/5	-8/5	12/5	0
cj		4/5	28/5	22/5	144

 

Оптимальное решение ПЗЛП: = (4, 4, 0, 0, 0, 0), = 144, оптимальное решение ДЗЛП: = (28/5, 4/5, 0, 0, 22/5),  = 144.

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

Остальные этапы задания выполняются аналогично рассмотренным выше.

3.2.2. Обоснование оптимального плана перевозок

На четырех базах (пунктах отправления) A₁, A₂, A₃, A₄ находится однородный груз в количествах, соответственно равных а₁, а₂, а₃ и а₄ единицам. Этот груз требуется перевести в три пункта назначения B₁, B₂, B₃, B₄ соответственно в количествах b ₁, b ₂, b ₃ и b ₄. единиц. Стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения составляет c_ij денежных единиц. Определить оптимальный план перевозок, при котором общая стоимость перевозок будет минимальной.

Обязательные требования к решению задачи.

1. Проверить разрешимость транспортной задачи. Если задача не разрешима, свести ее к закрытой задаче введением фиктивного пункта отправления (поставщика) или пункта назначения (потребителя).

2. Построить экономико-математическую модель транспортной задачи.

3. Найти начальное решение транспортной задачи и проверить его на вырожденность.

4. Решить транспортную задачу методом потенциалов.

5. Решить транспортную задачу в среде Microsoft Exсel, приложить отчет.

 

Исходные данные варианта 0:

Стоимость перевозки	В1	В2	В3	В4	Запасы
А1	с11 = 6	с12 = 10	с13 = 7	с14 = 5	а1 = 14
А2	с21 = 10	с22 = 7	с23 = 6	с24 = 9	а2 = 11
А3	с31 = 13	с32 = 14	с33 = 5	с34 = 7	а3 = 20
А4	с41 = 5	с42 = 10	с43 = 6	с44 = 4	а4 = 21
Потребности	b 1 = 15	b 2 = 16	b 3 = 15	b 4 = 20	-

 

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: