Методика решения задач линейного программирования
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
1. Решение задачи линейного программирования симплекс-методом
Постановка задачи
На предприятии выпускают n видов продукции . При ее изготовлении используются ресурсы P1, P2 и P3. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2 и b3. Расход ресурса i-го (i = 1, 2, 3) вида на единицу продукции j-го вида составляет aij ден. ед. Цена единицы продукции j-го вида равна cj ден. ед.
Требуется:
составить экономико-математическую модель задачи, позволяющую найти сбалансированный план выпуска продукции, обеспечивающий предприятию максимальный доход;
найти оптимальный план выпуска продукции по видам (дать содержательный ответ, раскрыв экономический смысл всех переменных, приведенных в решении задачи);
n = 3; b = ; A = ; c = (9 10 16).
Обозначим через x1, x2, x3 количество единиц продукции соответственно П1, П2, П3, планируемой к выпуску, а через f - величину дохода от реализации этой продукции. Тогда, учитывая цену единицы продукции П1, равную 9 ден. ед., единицы П2 - 10 ден. ед., единицы П3 - 16 ден. ед., запишем суммарную величину дохода - целевую функцию - в следующем виде:
f = 9x1 + 10x2 + 16x3.(1)
Переменные х1, х2, х3 должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса Р1 на выполнение плана (х1, х2, х3) составят
18x1 + 15x2 + 13x3 единиц,
где 18х1 - затраты ресурса Р1 на выпуск x1 единицы продукции П1; 15х2 - на выпуск единицы продукции П2; 12х3 - на выпуск единицы продукции П3. Указанная сумма не может превышать имеющийся запас Р1 в 360 единиц, т.е.
x1 + 15x2 + 13x3 360.(2)
Аналогично получаем ограничения по расходу ресурсов Р2, Р3:
x1 + 4x2 + 8x3 192.(3)
x1 + 3x2 + 3x3 180.(4)
По смыслу задачи переменные х1, х2, х3 не могут выражаться отрицательными числами, т.е.
xj 0 (j =)(5)
Соотношения (1) - (5) образуют экономико-математическую модель данной задачи. Итак, математически задача сводится к нахождению числовых значений х1*, х2*, х3* переменных х1, х2, х3, удовлетворяющих линейным неравенствам (2) - (5) и доставляющих максимум линейной функции (1).
Приведем модель задачи к канонической форме, преобразовать неравенства в эквивалентные уравнения. Для этого введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные x5, x6, х7. В результате получим:
f = 9x1 + 10x2 + 16x3 > max (6)
x1 + 15x2 + 13x3 + x4 = 360.
6x1 + 4x2 + 8x3 + x5 = 192.(7)
x1 + 3x2 + 3x3 + x6 = 180.
xj 0 (j =)(8)
Экономический смысл переменных х4, х5, х6 - возможные остатки ресурсов Р1, Р2, Р3 соответственно (резервы).
Решение задачи симплекс-методом
В канонической модели (6) - (8) каждая из переменных х4, х5, х6 является базисной, а остальные переменные - свободными. В связи с этим, в первую симплексную таблицу системы ограничительных уравнений (1.7) можно записать в виде, разрешенном относительно базиса х4, х5, х6 (табл. 1).
Таблица 1
x1x2x3x4x5x6x436018151310027,7x519264801024x618053300160f0-9-10-16000задача математический модель программирование
Все элементы столбца свободных членов положительны, поэтому содержащийся в табл. 1 план (0; 0; 0; 360; 192; 180) является опорным. Однако этот план не является оптимальным: в f-строке имеются отрицательные элементы.
Чтобы получить новый опорный план более близкий к оптимальному, выполним симплексное преобразование (табл. 1). С этой целью выберем переменные, участвующие в преобразовании базиса х4, х5, х6 в новый базис. Наибольший по модулю отрицательный элемент (-16) f-строки указывает, что в новый базис следует ввести переменную х3, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять третий столбец. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них:
min (360/13; 192/8; 180/3) = min (27,7; 24; 60) = 24.
Итак, из базиса надо исключить переменную, стоящую во второй (разрешающей) строке, т.е. х5. На пересечении разрешающих столбца и строки находится разрешающий элемент 8, с которым и выполняем симплекс-преобразование. Получаем табл. 2.
Таблица 2
x1x2x3x4x5x6x4488,258,501-1,62505,6x3240,750,5100,125048x61082,751,500-0,375172f3843-20020
Полученному плану X = (0; 0; 24; 48; 0; 108) соответствует значение целевой функции f(X1) = 384. В f-строке табл. 2 есть отрицательный элемент, равный -2, значит, полученный опорный план оптимальным не является.
Наибольший по модулю отрицательный элемент (-2) f-строки указывает, что в новый базис следует ввести переменную х2, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять второй столбец. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее:
min (48/8,5; 24/0,5; 108/1,5) = min (5,6; 48; 72) = 5,6.
Итак, из базиса надо исключить переменную, стоящую в первой (разрешающей) строке, т.е. х4. На пересечении разрешающих столбца и строки находится разрешающий элемент 8,5, с которым и выполняем следующее симплекс-преобразование.
В результате приходим к табл. 3.
Таблица 3
x1x2x3x4x5x6x25,6470,971100,118-0,1910x321,1760,26501-0,0590,2210x699,5291,29400-0,176-0,0881f395,34,941000,2351,6180
Полученному плану X2 = (0; 5,647; 21,176; 0; 0; 99,529) соответствует значение целевой функции f(X2) = 395,3. В результате получаем табл. 3, в f-строке которой отрицательных элементов нет.
Значит, опорный план X* = Х2 = (0; 5,647; 21,176; 0; 0; 99,529) является оптимальным, а соответствующее ему значение 395,3 целевой функции будет максимальным.
Итак, по оптимальному плану следует изготовить 5,647 ед. продукции вида П2 и 21,1