Применение графического метода и симплекс-метода для решения задач линейного программирования
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
p>
БПy1y2y3y4y5y6y7РешениеОтношениеf011/23/21/20-1/20-1-2/11y11-1/21/2-1/201/201-y705/21/21/2-1-1/2124/5?0-5/2-1/2-1/211/2-1--
На следующей итерации строка ? выходит из таблицы, так как в базисе не остается искусственных переменных:
БПy1y2y3y4y5y6y7РешениеОтношениеf002/5-3/511/53/5-11/5-27/59y1103/5-2/5-1/52/51/57/5-y2011/51/5-2/5-1/52/54/54
БПy1y2y3y4y5y6y7РешениеОтношениеf03108/50-1-3y11210-1013y40511-2-124
В строке f все коэффициенты неотрицательны кроме коэффициента при искусственной переменной y7, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, симплекс-методом получено оптимальное решение: Y = (3, 0, 0, 4, 0, 0, 0)T, X = (3, 0, 0), f = 3 + 5*0 + 2*0 = 3.
. Решение задачи двойственной к исходной
Приведем систему неравенств и целевую функцию к следующему виду:
Составим следующие векторы и матрицу коэффициентов:
c = (-1, -5, -2) -коэффициенты целевой функции;
b = (-2, -3) - свободные коэффициенты;
A = - коэффициенты из приведенной системы неравенств.
Сформулируем двойственную к исходной задачу на основе полученных коэффициентов. Свободные коэффициенты станут коэффициентами новой целевой функции, коэффициенты целевой функции станут новыми свободными коэффициентами, а коэффициенты системы неравенств образуют новую систему неравенств следующего вида:
;
Запишем задачу в канонической форме для возможности применить симплекс-метод, для этого введем три переменные w3, w4, w5:
= (0, 0, 1, 2, 5)T
Данная система является системой с базисом, следовательно, для решения можно применить симплекс-метод. Запишем начальную симплекс-таблицу:
БПw1w2w3w4w5РешениеОтношениеf-2-30000-w32110011/1 = 1w4-1201055/2 = 2.5w51100122/1 = 2
БПw1w2w3w4w5РешениеОтношениеf403003w2211001w4-50-2103w5-30-2010
В строке f все коэффициенты неотрицательны, следовательно, симплекс-методом получено оптимальное решение: W = (0, 1, 0, 3, 0)T, Z = (0, 1), f = 3.
. Решение транспортной задачи
Метод северо-западного угла:
Составим опорный план в соответствие с условием задачи:
МП/СП1001253252501002005 1008 1007103545042 25 -2 3255 100 + 6-125073 +59 150 -2 10030336-1Рисунок 1. Итерация №1
Проверка на сбалансированность: ?МП = 900, ?СП = 900 > они равны, следовательно, транспортная задача является закрытой.
Проверка на вырожденность: N = n + m - 1; N - количество базисных клеток = 7, n - количество строк = 3, m - количество столбцов = 5; 7 = 3 + 5 - 1 = 7 > транспортная задача является невырожденной.
Начальные затраты: Рнач = 500 + 800 + 50 + 650 + 500 + 1350 + 200 = 4050.
Проведем поэтапное улучшение опорного плана с помощью метода потенциалов. Добавим к опорному плану дополнительные строку и столбец (см. рисунок 1). Примем значение одной из получившихся дополнительных ячеек за 0. Рассчитаем по формуле: значение издержки = значение в ячейке дополнительной строки + значение ячейки дополнительного столбца остальные значения дополнительных ячеек. После этого, составим вспомогательную матрицу, значения в которой рассчитываются по следующей формуле: значение в матрице = значение издержки - (значение в ячейке дополнительной строки + значение ячейки дополнительного столбца).
0 -1 -1 -1
0 0 0 8
-3 -1 0 0
В данной вспомогательной матрице присутствуют отрицательные числа. Так как каждое число в матрице показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза, то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции (если число отрицательное, затраты уменьшаются). Из всех отрицательных значений выбираем наибольшее по модулю, так как ее воздействие на общие затраты является максимальным. Отметим знаком + в транспортной таблице ячейку соответствующую положению максимального по модулю отрицательного числа в вспомогательной матрице. Кроме нее мы пометим знаками - и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному + и -. То есть помеченные знаками клетки должны образовывать цикл (см. рисунок 1). Затем мы определим минимум из всех элементов, помеченных знаком -, и выберем одну ячейку, где этот минимум достигается. В нашем случае таковой является ячейка, содержащая 25 единиц груза. Следовательно, данная ячейка при пересчете должна стать свободной.
МП/СП1001253252501002005 1008 100 -7103 +5450422 3255 1256-425073 25 +59 1252 100 -003692
Р1 = 500 + 800 + 75 + 650 + 625 + 1125 + 200 = 3975. 4
минимальное количество груза в ячейке: 100
0 0 -4 -4 -
8 3 0 0 8
0 -1 0 0
МП/СП1001253252501002005 1008 7103 1005450422 325 -5 125 +6025073 125 5 +9 125 -2 0 40-125-2
Р2 = 500 + 0 + 375 + 650 + 625 + 1125 + 300 = 3575.
минимальное количество груза в ячейке: 125
0 4 0 0 0
4 3 0 0 8
3 0 -1 0 0
МП/СП1001253252501002005 1008 7103 1005450422 200 5 250 6125073 125 5 125 9 2 0 40-114-2
Ропт = 500 + 300 + 400 + 1250 + 375 + 625 = 3450.
4 1 1 0
2 0 0 1
0 0 1 0
В данной матрице не содержится отрицательных значений, следовательно, план улучшить нельзя, а значит достигнуто оптимальное решение.
Метод минимального элемента:
Составим опорный план в соответствие с условием задачи:
МП/СП1001253252501002005 1008 710 1003 545042 125 -2 325 5 + 6625073 0 +5 9 150 - 2 100 40-4-45-2
Проверка на вырожденность: N = n + m - 1; N - количество базисных клеток = 6, n - количество строк = 3, m - количество столбцов = 5; 6 3 + 5 - 1 = 7 > вводим фиктивную поставку.
Начальные