Математическое програмирование

Математическое программирование

Задача 1

Для производства двух видов изделий А и В используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2 часа, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час.

На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 48 часа, оборудование второго типа – 38 часов, оборудование третьего типа – 54 часов.

Прибыль от реализации единицы готового изделия А составляет 2 денежные единицы, а изделия В – 3 денежные единицы.

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

Решение.

Данная задача является задачей линейного программирования. Под планом производства понимается: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.

Прибыль рассчитывается по формуле:

Запишем математическую модель задачи:

Решим данную задачу графически.

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

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

График целевой функции передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (10 ; 14). В этой точке целевая функция будет достигать максимума.

Решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные .

Составляем симплекс-таблицу:

Базис	Cб	В	2	3	0	0	0
			А1	А2	А3	А4	А5
А3	0	48	2	2	1	0	0
А4	0	38	1	2	0	1	0
А5	0	54	3	1	0	0	1
Fi - Ci	0	-2	-3	0	0	0

В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – А₃ , А₄ , А₅ . Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.

В следующий столбец записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов А_i при i –й переменной.

Под столбцом свободных членов записывается начальная оценка

Остальные оценки записываются под столбцами соответствующих векторов .

Преобразуем симплекс-таблицу следующим образом:

Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.

Шаг 2: Для отрицательных оценок вычисляются величины:

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

Шаг 3: Вторая строка таблицы делится на 2

От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.

От элементов строки 3 отнимает соответствующие элементы строки 2.

От элементов строки 4 отнимает соответствующие элементы строки 2, умноженные на -3.

Базис	Cб	В	2	3	0	0	0
			А1	А2	А3	А4	А5
А3	0	10	1	0	1	-	0
А5	0	19	0,5	1	0	0,5	0
А2	3	35	2,5	0	0	-0,5	1
Fi - Ci	57	-0,5	0	0	1,5	0

Таким образом, новыми базисными переменными

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать