Laby_Mat_metody

71

Требуется а) определить план выпуска продукции, обеспечивающий максимальный до-

ход от ее реализации; б) сформулировать для данной задачи двойственную и определить ее опти-

мальное решение; в) найти интервалы устойчивости двойственных оценок по отношению к

изменениям ресурсов каждого типа; г) выявить изменение общей стоимости изготовляемой продукции, определя-

емой оптимальным планом ее производства при уменьшении количества ресурса типа I на 2100 ед. и увеличении ресурсов II и III типов соответственно на 800 и 600 ед. Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при их одновременном изменении в указанных размерах.

9. Для изготовления трех видов продукции A , B и C предприятие использует три типа ресурсов. Нормы расхода ресурсов каждого типа на единицу продукции, их наличие в распоряжении на предприятии, а также цена единицы продукции приведены в таблице.

Требуется а) определить план выпуска продукции, обеспечивающий максимальный до-

ход от ее реализации; б) сформулировать для данной задачи двойственную и определить ее опти-

мальное решение; в) найти интервалы устойчивости двойственных оценок по отношению к

изменениям ресурсов каждого типа;

72

г) выявить изменение общей стоимости изготовляемой продукции, определяемой оптимальным планом ее производства при уменьшении количества ресурса типа I на 15 ед. и увеличении ресурсов II и III типов соответственно на 10 и 20 ед. Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при их одновременном изменении в указанных размерах.

10. Для изготовления трех видов продукции A , B и C предприятие использует три типа ресурсов. Нормы расхода ресурсов каждого типа на единицу продукции, их наличие в распоряжении на предприятии, а также цена единицы продукции приведены в таблице.

Требуется а) определить план выпуска продукции, обеспечивающий максимальный до-

ход от ее реализации; б) сформулировать для данной задачи двойственную и определить ее опти-

мальное решение; в) найти интервалы устойчивости двойственных оценок по отношению к

изменениям ресурсов каждого типа; г) выявить изменение общей стоимости изготовляемой продукции, определя-

емой оптимальным планом ее производства при уменьшении количества ресурса типа I на 10 ед. и увеличении ресурсов II и III типов соответственно на 20 и 30 ед. Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при их одновременном изменении в указанных размерах.

11. Для изготовления трех видов продукции A , B и C предприятие использует три типа ресурсов. Нормы расхода ресурсов каждого типа на единицу продукции, их наличие в распоряжении на предприятии, а также цена единицы продукции приведены в таблице.

73

Требуется а) определить план выпуска продукции, обеспечивающий максимальный до-

ход от ее реализации; б) сформулировать для данной задачи двойственную и определить ее опти-

мальное решение; в) найти интервалы устойчивости двойственных оценок по отношению к

изменениям ресурсов каждого типа; г) выявить изменение общей стоимости изготовляемой продукции, определя-

емой оптимальным планом ее производства при уменьшении количества ресурса типа I на 40 ед. и увеличении ресурсов II и III типов соответственно на 80 и 60 ед. Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при их одновременном изменении в указанных размерах.

12. Для изготовления трех видов продукции A , B и C предприятие использует три типа ресурсов. Нормы расхода ресурсов каждого типа на единицу продукции, их наличие в распоряжении на предприятии, а также цена единицы продукции приведены в таблице.

Требуется а) определить план выпуска продукции, обеспечивающий максимальный до-

ход от ее реализации; б) сформулировать для данной задачи двойственную и определить ее опти-

мальное решение; в) найти интервалы устойчивости двойственных оценок по отношению к

изменениям ресурсов каждого типа;

74

г) выявить изменение общей стоимости изготовляемой продукции, определяемой оптимальным планом ее производства при уменьшении количества ресурса типа I на 10 ед. и увеличении ресурсов II и III типов соответственно на 20 и 30 ед. Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при их одновременном изменении в указанных размерах.

75

ЛАБОРАТОРНАЯ РАБОТА 9

Решение задач линейного программирования двойственным симплекс-методом

9.1 Цель работы

Приобретение навыков решения задач линейного программирования двойственным симплекс-методом.

9.2 Порядок выполнения работы

Для задачи, соответствующей номеру Вашего варианта, найдите оптимальное решение с помощью двойственного симплекс-метода. Составьте задачу, двойственную к исходной и, используя соответствие между переменными исходной и двойственной задач, найдите оптимальное решение двойственной задачи. Найдите оптимальное решение исходной и двойственной задач в табличном процессоре Microsoft Excel и продемонстрируйте их преподавателю. Оформите отчет по лабораторной работе, который должен содержать:

•титульный лист;

•решение исходной задачи двойственным симплекс-методом;

•двойственную задачу к исходной и ее оптимальное решение.

9.2.1Образец оформления решения

Задача 0.1 Решите задачу ЛП двойственным симплекс-методом:

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

77

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

{}

Значит столбец, соответствующий переменной x1 — разрешающий; 1 — разрешающий элемент.

Значит, переменную x6 исключаем из базиса, а переменную x1 включаем в базис.

После необходимых преобразований получим новую двойственную симплекс-таблицу (табл. 9.2):

Таблица 9.2

Последняя строка таблицы не содержит отрицательных оценок. Но так как в столбце значений свободных членов есть отрицательное число ( −12 ), то базисное решение не является оптимальным, и строка, соответствующая переменной x1 — разрешающая. Среди отрицательных элементов разрешающей строки выбираем минимальное двойственное отношение. Так как разрешающая строка содержит только один отрицательный элемент −4 , то минимальным двойственным отношением и будет −−34 = 34 . Тогда столбец, соответствующий переменной x2

— разрешающий; элемент −4 — разрешающий элемент. Значит, переменную x1 исключаем из базиса, а переменную x2 включаем в базис.

После необходимых преобразований получим новую двойственную симплекс-таблицу (табл. 9.3):

Таблица 9.3

Поскольку в столбце значений свободных членов все элементы больше нуля, то найден оптимальный план:

x = (0; 3; 0; 9; 30; 0), fmin = −21.

78

Тогда оптимальное решение задачи (9.1) имеет вид

x = (0; 3; 0; 9), fmin = −21.

Теперь составим задачу, двойственную к задаче (9.1). Для этого запишем задачу (9.1) в том виде, для которого удобнее применять алгоритм записи двойственной задачи:

С учетом того, что первое нетривиальное ограничение исходной задачи записано как равенство, на первую переменную двойственной задачи не накладывается условие неотрицательности. Тогда задача, двойственная к (9.1), имеет вид:

fb(z) = 18z1 − 24z2 + 12z3 → max;

Используя соответствие между переменными исходной и двойственной задач, найдем по последней симплекс-таблице (табл. 9.3) оптимальное решение двойственной к задаче (9.1):

()

79

9.3 Варианты задач к лабораторной работе

f(x) = 2x1 − 2x2 + 3x3 + 4x4 → max;

x1 + 2x2 + x3 + x4 ≤ 2,

52x1 − x2 + 2x3 − 3x4 ≥ 3,

x1 + 5x2 + 2x3 → min;3x1 + x2 + 2x3 ≥ 9,

8x1 + 2x2 + 2x3 ≥ 8,

x1 + 6x2 ≥ 12,xj ≥ 0 (j = 1, 3).

f(x) = −4x1 − 3x2 − 8x3 − 5x4 → max;

9x1 + x2 + 2x4 ≥ 4,

2x1 + x2 + 2x3 ≥ 6, xj ≥ 0 (j = 1, 4).

f(x) = 5x1 + 6x2 + x3 + x4 → min;

101, 5x1 + 3x2 − x3 + x4 ≥ 18,

3x1 + 2x3 − 4x4 ≥ 24, xj ≥ 0 (j = 1, 4).

12x1 − x2 + 4x3 + 5x4 ≥ 27,

2x1 + 3x2 − x3 + 4x4 ≥ 24, xj ≥ 0 (j = 1, 4).