Задача 18

Завод тяжелого машиностроения производит станки двух видов 3СБШ и 6СБШ. Для данного производства используется три вида сырья: металлопрокат в объеме 77 усл.ед., трубы в объеме 78 усл.ед, чугуны в объеме 54 усл.ед. На производство одного станка вида 3СБШ расходуется 1 усл.ед. металлопроката, 4 усл.ед. труб, 4 усл.ед. чугунов. Выпуск одного станка вида 6СБШ требует затрат металлопроката в количестве 7 усл.ед, труб в количестве 5 усл.ед. и 1 усл.ед. чугунов. Прибыль завода от реализации одного станка вида 3СБШ составит 3 ден.ед., а прибыль от реализации одного станка вида 6СБШ равна 4 ден.ед. Составит план производства станков указанного вида, который приносил бы заводу наибольшую прибыль.

РЕШЕНИЕ:

1) Построим математическую модель задачи.

Представим исходные данные в виде таблицы:

Вид сырья	Нормы расхода сырья на производство одного станка		Запасы сырья
	3СБШ	6СБШ
Металлопрокат, усл.ед.	1	7	77
Трубы, усл.ед.	4	5	78
Чугуны, усл.ед.	4	1	54
Прибыль от реализации одного станка, ден.ед.	3	4

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

Задача относится к классу оптимизационных задач. Математическая модель для задач такого класса состоит в построении целевой функции, для которой надо найти экстремум, при ограничениях.

Для решения поставленной задачи введем обозначения:

х₁ – количество производства станков вида 3СБШ;

х₂ – количество производства станков вида 6СБШ.

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

(ден.ед.)

Функция F называется целевой, ее следует максимизировать. Поэтому получаем:

На целевую функцию накладываются следующие ограничения:

а) ограничение по запасу металлопроката:

(усл.ед.);

б) ограничение по запасу труб:

(усл.ед.);

в) ограничение по запасу чугунов:

(усл.ед.);

д) условия неотрицательности количества производства:

.

е) условия целочисленности количества производства (с учетом того, что завод производит станки):

.

Математическая модель задачи: составить оптимальный план производства (х₁, х₂), обеспечивающий максимальную прибыль от реализации станков:

при ограничениях:

Математическая модель исходной задачи линейного программирования составлена.

2) Решим задачу геометрическим методом.

Построим множество допустимых решений или, что то же самое, область допустимых решений. Проведем перпендикулярные оси координат: горизонтальная — 0х₁, вертикальная — 0х₂. Условия неотрицательности переменных х₁  0 и х₂  0 показывают, что область допустимых решений будет лежать в первом квадранте системы координат.

Построим каждую прямую и определим полуплоскости, заданные неравенствами (рис. 1).

Построим уравнение по двум точкам.

	x1	x2
Первая точка	0	11
Вторая точка	77	0

Теперь нужно выбрать одну из двух полуплоскостей, на которые прямая разделила плоскость, и заштриховать эту полуплоскость. Чтобы правильно выбрать, возьмем точку плоскости, не лежащую на прямой, и подставим ее в неравенство. Например, точка не лежит на прямой:

Неравенство верное, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

Аналогично построим уравнение по двум точкам.

	x1	x2
Первая точка	0	15,6
Вторая точка	19,5	0

Определим полуплоскость, задаваемую неравенством: в полуплоскости ниже прямой.

Рис. 1. Область допустимых решений

Построим уравнение по двум точкам.

	x1	x2
Первая точка	0	54
Вторая точка	13,5	0

Определим полуплоскость, задаваемую неравенством: в полуплоскости ниже прямой.

Обозначим границы области многоугольника решений (рис. 2).

Рис. 2. Границы области многоугольника решений

Таким образом, областью допустимых решений (ОДР) является пятиугольник с вершинами ABCDЕ.

Рассмотрим целевую функцию задачи:

.

Построим прямую, отвечающую значению функции :

.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3; 4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией (рис. 3).

Рис. 3. Прямая целевой функции на максимум

Прямая пересекает область в точке С. Так как точка С получена в результате пересечения прямых, заданных уравнениями и , то ее координаты удовлетворяют уравнениям этих прямых.

Решаем систему уравнений:

Решив систему уравнений, получили:

x₁ = 7; x₂ = 10.

Найдем максимальное значение целевой функции:

(ден.ед.)

Ответ. ; . Для получения максимальной прибыли на заводе необходимо производить 7 станков вида 3СБШ и 10 станков вида 6СБШ. При использовании данного плана производства станков прибыль завода будет максимальной и составит 61 ден.ед.

РЕШЕНИЕ ГРАФИЧЕСКИМ СПОСОБОМ: