Файл: Решение Необходимо найти минимальное значение целевой функции f 2x 1 4x 2 min, при системе ограничений.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 107
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Контрольная работа
№ 1-10. Решите данную задачу линейного программирования графическим методом.
3.
Решение:
Необходимо найти минимальное значение целевой функции F = 2x1-4x2 → min, при системе ограничений:
3x1-4x2≥-40, (1)
6x1+5x2≤206, (2)
5x1-6x2≤100, (3)
3x1+8x2≥48, (4)
x1 ≥ 0, (5)
x2 ≥ 0, (6)
Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
или
Шаг №2. Границы области допустимых решений.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Шаг №3. Рассмотрим целевую функцию задачи F = 2x1-4x2 → min.
Построим прямую, отвечающую значению функции F = 2x1-4x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (2;-4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
3x1-4x2=-40
6x1+5x2=206
Решив систему уравнений
, получим: x1 = 16, x2 = 22
Откуда найдем минимальное значение целевой функции:
F(X) = 2*16 - 4*22 = -56
№ 11-20.
Для выпуска изделий двух типов А и В на предприятии используется три вида сырья. Предприятие обеспечено сырьем первого вида в количестве S1 кг, сырьем второго вида – S2 кг, сырьем третьего вида – S3 кг.
На производство одного изделия А необходимо затратить сырья первого вида a1 кг, сырья второго вида a2 кг, сырья третьего вида a3 кг. На производство одного изделия В необходимо затратить сырья первого вида b1 кг, сырья второго вида b2 кг, сырья третьего вида b3 кг. Прибыль от реализации одного изделия А составляет C1 руб., а изделия В – C2 руб.
Составьте план производства изделий А и В так, чтобы предприятие получило наибольшую прибыль от их реализации. Задачу решите симплексным методом.
14. a1 = 1, b1 = 4, S1 = 1140, C1 = 12,
a2 = 6, b2 = 7, S2 = 2420, C2 = 21,
a3 = 5, b3 = 4, S3 = 1650.
Решение:
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 12x1+21x2 при следующих условиях-ограничений.
x1+4x2≤1140
6x1+7x2≤2420
5x1+4x2≤1650
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
x1+4x2+x3 = 1140
6x1+7x2+x4 = 2420
5x1+4x2+x5 = 1650
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные
равны 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. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
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. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 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. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (285 : 1/4 , 425 : 41/4 , 510 : 4 ) = 100
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (41/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. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=41/4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.