Фирма производит и продает два типа товаров. Фирма получает прибыль в размере 15 тыс. р. от производства и продажи каждой единицы товара 1 и в размере 4 тыс. р. от производства и продажи каждой единицы товара 2. Фирма состоит из трех подразделений. Затраты труда (чел-дни) на производство этих товаров в каждом из подразделений указаны в таблице.
Подразделение Трудозатраты, чел-дней на 1 шт.
Товар 1 Товар 2
1 5 2
2 3 2
3 6 6
Руководство рассчитало, что в следующем месяце фирма будет располагать следующими возможностями обеспечения производства трудозатратами: 1000 чел-дней в подразделении 1, 500 – подразделении 2 и 2100 – в подразделении 3. Составить задачу линейного программирования и найти ее решение. Числовые значения взять из таблицы для каждого номера задачи. Составить двойственную задачу, решить ее, используя теоремы двойственности и отчет Устойчивость в Excel.
Решение
Пусть необходимо произвести товара 1 – х1, товара 2 – х2, тогда ограничения
по подразделению 1:5x1+2x2≤1000,по подразделению 2:3x1+2x2≤500,по подразделению 3:6x1+6x2≤2100,
по неотрицательности переменных:
х1>0,
х2>0.
Прибыль определяется как F(X)=15x1+4x2, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F(X) = 15x1+4x2 → max
5x1+2x2≤1000,3x1+2x2≤500,6x1+6x2≤2100,х1>0,
х2>0.
Решаем задачу симплекс-методом с использованием симплекс-таблицы.
Для построения опорного плана 1 систему неравенств приводим к системе уравнений путем введения дополнительных переменных (переходим к канонической форме).
В 1-м неравенстве смысла (≤) введем неотрицательную базисную переменную x3, во 2-м неравенстве смысла (≤) введем неотрицательную базисную переменную x4, в 3-м неравенстве смысла (≤) введем неотрицательную базисную переменную x5.
5x1+2x2+x3 = 1000
3x1+2x2+x4 = 500
6x1+6x2+x5 = 2100
Матрица коэффициентов A = a(ij) системы уравнений принимает вид:
A = 5 2 1 0 0
3 2 0 1 0
6 6 0 0 1
Решаем систему уравнений относительно базисных переменных: x3, x4, x5
Полагаем, что свободные переменные равны 0, получим опорный план 1: X0 = (0,0,1000,500,2100)
БП B x1 x2 x3 x4 x5
x3 1000 5 2 1 0 0
x4 500 3 2 0 1 0
x5 2100 6 6 0 0 1
∆ 0 -15 -4 0 0 0
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
БП B x1↓ x2 x3 x4 x5 min
x3 1000 5 2 1 0 0 200
←x4 500 3 2 0 1 0 500/3
x5 2100 6 6 0 0 1 350
∆ 0 -15 -4 0 0 0
БП B x1 x2 x3 x4 x5
x3 500/3 0 -4/3 1 -5/3 0
x1 500/3 1 2/3 0 1/3 0
x5 1100 0 2 0 -2 1
∆ 2500 0 6 0 5 0
Т.к
Задать вопрос
на новый заказ в Автор24.
