Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2

Экономико – математическую модель задачи
Пусть продукция производится в количестве:
1-й вид Изделие 1– x1 единиц, 2-й вид Изделие 2– x2 единиц.
Тогда стоимость произведенной продукции выражается целевой функцией:
f(x1,x2)=с1 x1+с2 x2,
для которой необходимо найти максимум.
При этом следует учесть ограничения по запасам сырья:
а 11 x1+а 12 x2 b1,
а 21 x1+а 22 x2 b2,
а 31 x1+а 32 x2 b3
и по смыслу задачи x1, x2 должны быть неотрицательными и целыми:
x10, x2 0.
план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования
Выполнение.
Возьмем произвольные значения для неизвестных:
А=1,21,92,31,80,10,7
B=3757,67
C=(25000;50000)
Необходимо найти максимальное значение целевой функции F = 25000x1+50000x2 → max, при системе ограничений:1.2x1+1.9x2≤37, (1)2.3x1+1.8x2≤56.6, (2)0.1x1+0.7x2≤7, (3)x1 ≥ 0, (4)x2 ≥ 0, (5)Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).Построим уравнение 1.2x1+1.9x2 = 37 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 19.47. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 30.83. Соединяем точку (0;19.47) с (30.83;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1.2 • 0 + 1.9 • 0 - 37 ≤ 0, т.е. 1.2x1+1.9x2 - 37≤ 0 в полуплоскости ниже прямой.Построим уравнение 2.3x1+1.8x2 = 56.6 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 31.44. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 24.61. Соединяем точку (0;31.44) с (24.61;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:2.3 • 0 + 1.8 • 0 - 56.6 ≤ 0, т.е. 2.3x1+1.8x2 - 56.6≤ 0 в полуплоскости ниже прямой.Построим уравнение 0.1x1+0.7x2 = 7 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 10. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 70. Соединяем точку (0;10) с (70;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:0.1 • 0 + 0.7 • 0 - 7 ≤ 0, т.е. 0.1x1+0.7x2 - 7≤ 0 в полуплоскости ниже прямой.илиШаг №2. Границы области допустимых решений.Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.Обозначим границы области многоугольника решений.Шаг №3. Рассмотрим целевую функцию задачи F = 25000x1+50000x2 → max.Построим прямую, отвечающую значению функции F = 25000x1+50000x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (25000;50000) . Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:2.3x1+1.8x2=56.60.1x1+0.7x2=7Решив систему уравнений, получим: x1 = 18.8951, x2 = 7.3007Откуда найдем максимальное значение целевой функции:F(X) = 25000*18.8951 + 50000*7.3007 = 837412.5
план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования
Выполнение.
Возьмем произвольные значения для неизвестных:
А=1,21,92,31,80,10,7
B=3757,67
C=(25000;50000)
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.Определим максимальное значение целевой функции F(X) = 25000x1+50000x2 при следующих условиях-ограничений.1.2x1+1.9x2≤372.3x1+1.8x2≤56.60.1x1+0.7x2≤7Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.1.2x1+1.9x2+x3 = 372.3x1+1.8x2+x4 = 56.60.1x1+0.7x2+x5 = 7Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1,2 1,9 1 0 0
2,3 1,8 0 1 0
0,1 0,7 0 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.Решим систему уравнений относительно базисных переменных: x3, x4, x5Полагая, что свободные переменные равны 0, получим первый опорный план:X0 = (0,0,37,56.6,7)Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x3 37 1.2 1.9 1 0 0
x4 56.6 2.3 1.8 0 1 0
x5 7 0.1 0.7 0 0 1
F(X0) 0 -25000 -50000 0 0 0
Переходим к основному алгоритму симплекс-метода.Итерация №0.1. Проверка критерия оптимальности.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.2. Определение новой базисной переменной.В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:min (37 : 1.9 , 56.6 : 1.8 , 7 : 0.7 ) = 10Следовательно, 3-ая строка является ведущей.Разрешающий элемент равен (0.7) и находится на пересечении ведущего столбца и ведущей строки.
сi сj 25000 50000 0 0 0 f(x) min
Базисные переменные x1 x2 x3 x4 x5 bi bi/hij
0 x3 1.2 1.9 1 0 0 37 37:1.9
0 x4 2.3 1.8 0 1 0 56.6 56.6:1.8
0 x5 ← 0.1 0 0 0 1 7 7:0
∆1
-25000 -50000 ↑ 0 0 0 0
4