Контрольная работа № 1-10. Решите данную задачу линейного программирования графическим методом. 3. Решение:Необходимо найти минимальное значение целевой функции F = 2x₁-4x₂ → min, при системе ограничений: 3x₁-4x₂≥-40, (1) 6x₁+5x₂≤206, (2) 5x₁-6x₂≤100, (3) 3x₁+8x₂≥48, (4) x₁ ≥ 0, (5) x₂ ≥ 0, (6) Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). или Шаг №2. Границы области допустимых решений. Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений. Шаг №3. Рассмотрим целевую функцию задачи F = 2x₁-4x₂ → min. Построим прямую, отвечающую значению функции F = 2x₁-4x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (2;-4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией. Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых: 3x₁-4x₂=-40 6x₁+5x₂=206 Решив систему уравнений

---

, получим: x₁ = 16, x₂ = 22

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

F(X) = 2*16 - 4*22 = -56

№ 11-20.

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

На производство одного изделия А необходимо затратить сырья первого вида a₁ кг, сырья второго вида a₂ кг, сырья третьего вида a₃ кг. На производство одного изделия В необходимо затратить сырья первого вида b₁ кг, сырья второго вида b₂ кг, сырья третьего вида b₃ кг. Прибыль от реализации одного изделия А составляет C₁ руб., а изделия В – C₂ руб.

Составьте план производства изделий А и В так, чтобы предприятие получило наибольшую прибыль от их реализации. Задачу решите симплексным методом.
14. a₁ = 1, b₁ = 4, S₁ = 1140, C₁ = 12,

a₂ = 6, b₂ = 7, S₂ = 2420, C₂ = 21,

a₃ = 5, b₃ = 4, S₃ = 1650.

Решение:

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

Определим максимальное значение целевой функции F(X) = 12x₁+21x₂ при следующих условиях-ограничений.

x₁+4x₂≤1140

6x₁+7x₂≤2420

5x₁+4x₂≤1650

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅.

x₁+4x₂+x₃ = 1140

6x₁+7x₂+x₄ = 2420

5x₁+4x₂+x₅ = 1650

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅

Полагая, что свободные переменные

---

равны 0, получим первый опорный план:

X0 = (0,0,1140,2420,1650)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5
x3	1140	1	4	1	0	0
x4	2420	6	7	0	1	0
x5	1650	5	4	0	0	1
F(X0)	0	-12	-21	0	0	0

Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i2и из них выберем наименьшее: min (1140 : 4 , 2420 : 7 , 1650 : 4 ) = 285 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x3	1140	1	4	1	0	0	285
x4	2420	6	7	0	1	0	2420/7
x5	1650	5	4	0	0	1	825/2
F(X1)	0	-12	-21	0	0	0

---

4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x₃ в план 1 войдет переменная x₂. Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₃ плана 0 на разрешающий элемент РЭ=4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂ записываем нули. Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5
1140 : 4	1 : 4	4 : 4	1 : 4	0 : 4	0 : 4
2420-(1140 • 7):4	6-(1 • 7):4	7-(4 • 7):4	0-(1 • 7):4	1-(0 • 7):4	0-(0 • 7):4
1650-(1140 • 4):4	5-(1 • 4):4	4-(4 • 4):4	0-(1 • 4):4	0-(0 • 4):4	1-(0 • 4):4
0-(1140 • -21):4	-12-(1 • -21):4	-21-(4 • -21):4	0-(1 • -21):4	0-(0 • -21):4	0-(0 • -21):4

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x2	285	1/4	1	1/4	0	0
x4	425	17/4	0	-7/4	1	0
x5	510	4	0	-1	0	1
F(X1)	5985	-27/4	0	21/4	0	0

---

Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i1и из них выберем наименьшее: min (285 : ¹/₄ , 425 : 4¹/₄ , 510 : 4 ) = 100 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (4¹/₄) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x2	285	1/4	1	1/4	0	0	1140
x4	425	17/4	0	-7/4	1	0	100
x5	510	4	0	-1	0	1	255/2
F(X2)	5985	-27/4	0	21/4	0	0

4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 2 войдет переменная x₁. Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=4¹/₄. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₁ записываем нули. Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

---

Смотрите также файлы

• Охарактеризуйте основные требования к выразительному чтению педагога, дошкольника и учащегося начальной школы.docx

• Вид практикитжірибе трі Студент ваше фио факультет Сестринское делоМейіргер ісі Курс 3 группатоп 329б количество часовСаат саны 150.docx

• Программное содержание.docx

• 1тапсырма. Бастауыш білім берудегі шетелдік тжірибеге шолу теориялы материалын зерделеіз. Зерделеген материал негізінде ментальді карта зірлеіз. 1кн.docx

• Тест начат Пятница, 30 декабря 2022, 02 19 Состояние.docx