Решение задачи по составлению плана производства изделий А и В, обеспечивающего максимальную прибыль.
Нам нужно найти такой план производства, который принесет максимальную прибыль, учитывая ограничения по сырью.
1. Математическая модель задачи
Пусть \(x_1\) – количество изделий типа А, а \(x_2\) – количество изделий типа В.
Целевая функция (прибыль, которую нужно максимизировать):
\[Z = 6x_1 + 3x_2 \to \max\]
Ограничения по сырью:
1. По сырью первого вида: \(6x_1 + 2x_2 \le 600\)
2. По сырью второго вида: \(4x_1 + 3x_2 \le 520\)
3. По сырью третьего вида: \(3x_1 + 4x_2 \le 600\)
Также, количество изделий не может быть отрицательным:
\[x_1 \ge 0, x_2 \ge 0\]
2. Геометрический метод решения
Для решения геометрическим методом, построим область допустимых решений (ОДР) на координатной плоскости. Каждое неравенство-ограничение представляет собой полуплоскость. Пересечение этих полуплоскостей и будет ОДР.
1. \(6x_1 + 2x_2 \le 600\)
Для построения прямой, возьмем равенство: \(6x_1 + 2x_2 = 600\).
Если \(x_1 = 0\), то \(2x_2 = 600 \Rightarrow x_2 = 300\). Точка (0, 300).
Если \(x_2 = 0\), то \(6x_1 = 600 \Rightarrow x_1 = 100\). Точка (100, 0).
2. \(4x_1 + 3x_2 \le 520\)
Для построения прямой, возьмем равенство: \(4x_1 + 3x_2 = 520\).
Если \(x_1 = 0\), то \(3x_2 = 520 \Rightarrow x_2 = 173.33\). Точка (0, 173.33).
Если \(x_2 = 0\), то \(4x_1 = 520 \Rightarrow x_1 = 130\). Точка (130, 0).
3. \(3x_1 + 4x_2 \le 600\)
Для построения прямой, возьмем равенство: \(3x_1 + 4x_2 = 600\).
Если \(x_1 = 0\), то \(4x_2 = 600 \Rightarrow x_2 = 150\). Точка (0, 150).
Если \(x_2 = 0\), то \(3x_1 = 600 \Rightarrow x_1 = 200\). Точка (200, 0).
4. \(x_1 \ge 0, x_2 \ge 0\) – это первая четверть координатной плоскости.
Построим эти прямые и найдем область, которая удовлетворяет всем неравенствам. Это будет многоугольник. Вершины этого многоугольника являются потенциальными точками оптимума.
Найдем координаты вершин ОДР:
* Точка A: (0, 0). Прибыль \(Z = 6 \cdot 0 + 3 \cdot 0 = 0\).
* Точка B: Пересечение оси \(x_1\) (\(x_2 = 0\)) и прямой \(4x_1 + 3x_2 = 520\).
\(4x_1 = 520 \Rightarrow x_1 = 130\). Точка (130, 0).
Проверим, удовлетворяет ли эта точка другим ограничениям:
\(6 \cdot 130 + 2 \cdot 0 = 780 \not\le 600\). Значит, точка (130, 0) не является вершиной ОДР.
Вершина на оси \(x_1\) будет от прямой \(6x_1 + 2x_2 = 600\), то есть (100, 0).
Точка B: (100, 0). Прибыль \(Z = 6 \cdot 100 + 3 \cdot 0 = 600\).
* Точка C: Пересечение прямых \(6x_1 + 2x_2 = 600\) и \(4x_1 + 3x_2 = 520\).
Умножим первое уравнение на 3, второе на 2:
\(18x_1 + 6x_2 = 1800\)
\(8x_1 + 6x_2 = 1040\)
Вычтем второе из первого:
\(10x_1 = 760 \Rightarrow x_1 = 76\)
Подставим \(x_1 = 76\) в \(6x_1 + 2x_2 = 600\):
\(6 \cdot 76 + 2x_2 = 600\)
\(456 + 2x_2 = 600\)
\(2x_2 = 144 \Rightarrow x_2 = 72\)
Точка C: (76, 72).
Проверим третье ограничение: \(3 \cdot 76 + 4 \cdot 72 = 228 + 288 = 516 \le 600\). Удовлетворяет.
Прибыль \(Z = 6 \cdot 76 + 3 \cdot 72 = 456 + 216 = 672\).
* Точка D: Пересечение прямых \(4x_1 + 3x_2 = 520\) и \(3x_1 + 4x_2 = 600\).
Умножим первое уравнение на 4, второе на 3:
\(16x_1 + 12x_2 = 2080\)
\(9x_1 + 12x_2 = 1800\)
Вычтем второе из первого:
\(7x_1 = 280 \Rightarrow x_1 = 40\)
Подставим \(x_1 = 40\) в \(4x_1 + 3x_2 = 520\):
\(4 \cdot 40 + 3x_2 = 520\)
\(160 + 3x_2 = 520\)
\(3x_2 = 360 \Rightarrow x_2 = 120\)
Точка D: (40, 120).
Проверим первое ограничение: \(6 \cdot 40 + 2 \cdot 120 = 240 + 240 = 480 \le 600\). Удовлетворяет.
Прибыль \(Z = 6 \cdot 40 + 3 \cdot 120 = 240 + 360 = 600\).
* Точка E: Пересечение оси \(x_2\) (\(x_1 = 0\)) и прямой \(3x_1 + 4x_2 = 600\).
\(4x_2 = 600 \Rightarrow x_2 = 150\). Точка (0, 150).
Проверим, удовлетворяет ли эта точка другим ограничениям:
\(6 \cdot 0 + 2 \cdot 150 = 300 \le 600\). Удовлетворяет.
\(4 \cdot 0 + 3 \cdot 150 = 450 \le 520\). Удовлетворяет.
Точка E: (0, 150). Прибыль \(Z = 6 \cdot 0 + 3 \cdot 150 = 450\).
Сравниваем значения прибыли в вершинах:
* A (0, 0): \(Z = 0\)
* B (100, 0): \(Z = 600\)
* C (76, 72): \(Z = 672\)
* D (40, 120): \(Z = 600\)
* E (0, 150): \(Z = 450\)
Максимальная прибыль достигается в точке C (76, 72) и составляет 672 ден.ед.
Таким образом, оптимальный план производства: 76 изделий типа А и 72 изделия типа В.
3. Симплекс-метод решения
Для симплекс-метода сначала приведем задачу к каноническому виду, введя дополнительные переменные \(x_3, x_4, x_5\) для каждого ограничения. Эти переменные будут представлять собой остаток сырья.
\[6x_1 + 2x_2 + x_3 = 600\]
\[4x_1 + 3x_2 + x_4 = 520\]
\[3x_1 + 4x_2 + x_5 = 600\]
\[x_1, x_2, x_3, x_4, x_5 \ge 0\]
Целевая функция: \(Z = 6x_1 + 3x_2 + 0x_3 + 0x_4 + 0x_5 \to \max\)
Перепишем целевую функцию для симплекс-таблицы:
\[Z - 6x_1 - 3x_2 - 0x_3 - 0x_4 - 0x_5 = 0\]
Первая симплекс-таблица
| Базис | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | Свободные члены |
|---|---|---|---|---|---|---|
| \(x_3\) | 6 | 2 | 1 | 0 | 0 | 600 |
| \(x_4\) | 4 | 3 | 0 | 1 | 0 | 520 |
| \(x_5\) | 3 | 4 | 0 | 0 | 1 | 600 |
| Z | -6 | -3 | 0 | 0 | 0 | 0 |
Выбираем ведущий столбец: Наиболее отрицательный коэффициент в строке Z – это -6 (столбец \(x_1\)).
Выбираем ведущую строку: Делим свободные члены на соответствующие элементы ведущего столбца:
\(600 / 6 = 100\)
\(520 / 4 = 130\)
\(600 / 3 = 200\)
Минимальное положительное отношение – 100. Ведущая строка – первая (строка \(x_3\)).
Ведущий элемент – 6.
Вторая симплекс-таблица
Выполняем преобразования:
1. Делим ведущую строку на ведущий элемент (6):
\(x_1\)-строка: \(1, 1/3, 1/6, 0, 0, 100\)
2. Обнуляем остальные элементы ведущего столбца:
* Для \(x_4\)-строки: \(R_2' = R_2 - 4R_1'\)
\(x_1\): \(4 - 4 \cdot 1 = 0\)
\(x_2\): \(3 - 4 \cdot (1/3) = 3 - 4/3 = 5/3\)
\(x_3\): \(0 - 4 \cdot (1/6) = -4/6 = -2/3\)
\(x_4\): \(1 - 4 \cdot 0 = 1\)
\(x_5\): \(0 - 4 \cdot 0 = 0\)
Свободный член: \(520 - 4 \cdot 100 = 120\)
* Для \(x_5\)-строки: \(R_3' = R_3 - 3R_1'\)
\(x_1\): \(3 - 3 \cdot 1 = 0\)
\(x_2\): \(4 - 3 \cdot (1/3) = 4 - 1 = 3\)
\(x_3\): \(0 - 3 \cdot (1/6) = -3/6 = -1/2\)
\(x_4\): \(0 - 3 \cdot 0 = 0\)
\(x_5\): \(1 - 3 \cdot 0 = 1\)
Свободный член: \(600 - 3 \cdot 100 = 300\)
* Для Z-строки: \(R_Z' = R_Z - (-6)R_1' = R_Z + 6R_1'\)
\(x_1\): \(-6 + 6 \cdot 1 = 0\)
\(x_2\): \(-3 + 6 \cdot (1/3) = -3 + 2 = -1\)
\(x_3\): \(0 + 6 \cdot (1/6) = 1\)
\(x_4\): \(0 + 6 \cdot 0 = 0\)
\(x_5\): \(0 + 6 \cdot 0 = 0\)
Свободный член: \(0 + 6 \cdot 100 = 600\)
| Базис | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | Свободные члены |
|---|---|---|---|---|---|---|
| \(x_1\) | 1 | 1/3 | 1/6 | 0 | 0 | 100 |
| \(x_4\) | 0 | 5/3 | -2/3 | 1 | 0 | 120 |
| \(x_5\) | 0 | 3 | -1/2 | 0 | 1 | 300 |
| Z | 0 | -1 | 1 | 0 | 0 | 600 |
В строке Z есть отрицательный коэффициент (-1), значит, решение не оптимально.
Выбираем ведущий столбец: Столбец \(x_2\).
Выбираем ведущую строку:
\(100 / (1/3) = 300\)
\(120 / (5/3) = 120 \cdot 3/5 = 72\)
\(300 / 3 = 100\)
Минимальное положительное отношение – 72. Ведущая строка – вторая (строка \(x_4\)).
Ведущий элемент – 5/3.
Третья симплекс-таблица
Выполняем преобразования:
1. Делим ведущую строку на ведущий элемент (5/3):
\(x_2\)-строка: \(0, 1, -2/3 \cdot 3/5, 1 \cdot 3/5, 0, 120 \cdot 3/5\)
\(x_2\)-строка: \(0, 1, -2/5, 3/5, 0, 72\)
2. Обнуляем остальные элементы ведущего столбца:
* Для \(x_1\)-строки: \(R_1' = R_1 - (1/3)R_2'\)
\(x_1\): \(1 - (1/3) \cdot 0 = 1\)
\(x_2\): \(1/3 - (1/3) \cdot 1 = 0\)
\(x_3\): \(1/6 - (1/3) \cdot (-2/5) = 1/6 + 2/15 = 5/30 + 4/30 = 9/30 = 3/10\)
\(x_4\): \(0 - (1/3) \cdot (3/5) = -1/5\)
\(x_5\): \(0 - (1/3) \cdot 0 = 0\)
Свободный член: \(100 - (1/3) \cdot 72 = 100 - 24 = 76\)
* Для \(x_5\)-строки: \(R_3' = R_3 - 3R_2'\)
\(x_1\): \(0 - 3 \cdot 0 = 0\)
\(x_2\): \(3 - 3 \cdot 1 = 0\)
\(x_3\): \(-1/2 - 3 \cdot (-2/5) = -1/2 + 6/5 = -5/10 + 12/10 = 7/10\)
\(x_4\): \(0 - 3 \cdot (3/5) = -9/5\)
\(x_5\): \(1 - 3 \cdot 0 = 1\)
Свободный член: \(300 - 3 \cdot 72 = 300 - 216 = 84\)
* Для Z-строки: \(R_Z' = R_Z - (-1)R_2' = R_Z + R_2'\)
\(x_1\): \(0 + 0 = 0\)
\(x_2\): \(-1 + 1 = 0\)
\(x_3\): \(1 + (-2/5) = 3/5\)
\(x_4\): \(0 + 3/5 = 3/5\)
\(x_5\): \(0 + 0 = 0\)
Свободный член: \(600 + 72 = 672\)
| Базис | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | Свободные члены |
|---|---|---|---|---|---|---|
| \(x_1\) | 1 | 0 | 3/10 | -1/5 | 0 | 76 |
| \(x_2\) | 0 | 1 | -2/5 | 3/5 | 0 | 72 |
| \(x_5\) | 0 | 0 | 7/10 | -9/5 | 1 | 84 |
| Z | 0 | 0 | 3/5 | 3/5 | 0 | 672 |
Все коэффициенты в строке Z неотрицательны, значит, найдено оптимальное решение.
Оптимальный план: \(x_1 = 76\), \(x_2 = 72\).
Максимальная прибыль \(Z = 672\).
Остатки сырья: \(x_3 = 0\) (сырье 1 полностью использовано), \(x_4 = 0\) (сырье 2 полностью использовано), \(x_5 = 84\) (остаток сырья 3).
Результаты геометрического и симплекс-методов совпадают.
4. Транспортная задача (Опорные планы и проверка на оптимальность)
В данном случае, задача не является классической транспортной задачей. У нас задача линейного программирования на максимизацию прибыли с ограничениями по ресурсам. Методы "северо-западного угла", "минимальной стоимости", "двойного предпочтения" и "Фогеля" применяются для нахождения начального опорного плана в транспортных задачах, где есть пункты отправления и пункты назначения, и нужно минимизировать затраты на перевозку.
Наша задача не имеет такой структуры. Поэтому применение этих методов здесь некорректно.
Метод потенциалов также используется для проверки оптимальности опорного плана в транспортных задачах.
Возможно, в условии задачи произошла путаница, и эти методы были указаны по ошибке, или же предполагалось, что нужно решить другую задачу, которая имеет структуру транспортной.
Если бы задача была транспортной, то:
* Метод северо-западного угла: Начинаем заполнение таблицы с левого верхнего угла, удовлетворяя потребности и запасы по очереди.
* Метод минимальной стоимости: Начинаем заполнение с ячейки с наименьшей стоимостью.
* Метод двойного предпочтения (или метод наименьшей стоимости с учетом штрафов): Выбираем ячейку с наименьшей стоимостью, но при этом учитываем "штрафы" за неиспользование других дешевых маршрутов.
* Метод Фогеля (метод аппроксимации): Вычисляем "штрафы" для каждой строки и столбца (разница между двумя наименьшими стоимостями), выбираем наибольший штраф и заполняем соответствующую ячейку с минимальной стоимостью.
Поскольку наша задача не является транспортной, эти методы не применимы.
Вывод
Оптимальный план производства:
* Изделий типа А: 76 штук
* Изделий типа В: 72 штуки
Максимальная прибыль от реализации: 672 денежных единицы.
Остатки сырья:
* Сырье первого вида: 0 кг
* Сырье второго вида: 0 кг
* Сырье третьего вида: 84 кг
