ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.12.2023
Просмотров: 57
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Задание № 1. реализации единицы продукции, руб">Составить план производства продукции, обеспечив максимум прибыли, учитывая ограничения, заданные в таблице 1.
Таблица 1. Линейная оптимизация
| | Расход сырья (доли) | Прибыль от реализации единицы продукции, руб. | |||
| Сырье 1 | Сырье 2 | Сырье 3 | Сырье 4 | ||
| Продукт 1 | 0,2 | 0,3 | 0,1 | 0,4 | 120 |
| Продукт 2 | 0,4 | 0,1 | 0,3 | 0,2 | 150 |
| Продукт 3 | 0,6 | 0,1 | 0,1 | 0,2 | 110 |
| Наличие сырья на складе, кг | 850 | 640 | 730 | 1000 | |
Решение:
F(X) = 850x1+640x2+730x3+1000x4 → max при ограничениях:
1/5x1+3/10x2+1/10x3+2/5x4≤120
2/5x1+1/10x2+3/10x3+1/5x4≤150
3/5x1+1/10x2+1/10x3+1/5x4≤110
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
F(X) = 850x1+640x2+730x3+1000x4
В 1-м неравенстве смысла (≤) вводим базисную переменную x5.
В 2-м неравенстве смысла (≤) вводим базисную переменную x6.
В 3-м неравенстве смысла (≤) вводим базисную переменную x7.
1/5x1+3/10x2+1/10x3+2/5x4+x5 = 120
2/5x1+1/10x2+3/10x3+1/5x4+x6 = 150
3/5x1+1/10x2+1/10x3+1/5x4+x7 = 110
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 1/5 | 3/10 | 1/10 | 2/5 | 1 | 0 | 0 | 120 |
| 2/5 | 1/10 | 3/10 | 1/5 | 0 | 1 | 0 | 150 |
| 3/5 | 1/10 | 1/10 | 1/5 | 0 | 0 | 1 | 110 |
1. В качестве базовой переменной можно выбрать x5.
2. В качестве базовой переменной можно выбрать x6.
3. В качестве базовой переменной можно выбрать x7.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (5,6,7).
Соответствующие уравнения имеют вид:
1/5x1+3/10x2+1/10x3+2/5x4+x5 = 120
2/5x1+1/10x2+3/10x3+1/5x4+x6 = 150
3/5x1+1/10x2+1/10x3+1/5x4+x7 = 110
Выразим базисные переменные через остальные:
x5 = -1/5x1-3/10x2-1/10x3-2/5x4+120
x6 = -2/5x1-1/10x2-3/10x3-1/5x4+150
x7 = -3/5x1-1/10x2-1/10x3-1/5x4+110
Подставим их в целевую функцию:
F(X) = 850x1+640x2+730x3+1000x4 или
F(X) = 850x1+640x2+730x3+1000x4 → max
Система неравенств:
-1/5x1-3/10x2-1/10x3-2/5x4+120 ≥ 0
-2/5x1-1/10x2-3/10x3-1/5x4+150 ≥ 0
-3/5x1-1/10x2-1/10x3-1/5x4+110 ≥ 0
Приводим систему неравенств к следующему виду:
1/5x1+3/10x2+1/10x3+2/5x4 ≤ 120
2/5x1+1/10x2+3/10x3+1/5x4 ≤ 150
3/5x1+1/10x2+1/10x3+1/5x4 ≤ 110
F(X) = 850x1+640x2+730x3+1000x4 → max
Упростим систему.
2x1+3x2+x3+4x4 ≤ 1200
4x1+x2+3x3+2x4 ≤ 1500
6x1+x2+x3+2x4 ≤ 1100
F(X) = 850x1+640x2+730x3+1000x4 → max
Если задача ЛП решается на поиск min-го значения, то стандартная форма будет иметь следующий вид:
-2x1-3x2-x3-4x4 ≤ -1200
-4x1-x2-3x3-2x4 ≤ -1500
-6x1-x2-x3-2x4 ≤ -1100
F(X) = -850x1-640x2-730x3-1000x4 → min
Решим прямую задачу линейного программирования симплекс-методом.
Определим максимальное значение целевой функции F(X) = 850x1+640x2+730x3+1000x4 при следующих условиях-ограничений.
1/5x1+3/10x2
+1/10x3+2/5x4+x5+120=120
2/5x1+1/10x2+3/10x3+1/5x4+x6+150=150
3/5x1+1/10x2+1/10x3+1/5x4+x7+110=110
Расширенная матрица системы ограничений-равенств данной задачи:
| 1/5 | 3/10 | 1/10 | 2/5 | 1 | 0 | 0 | 120 |
| 2/5 | 1/10 | 3/10 | 1/5 | 0 | 1 | 0 | 150 |
| 3/5 | 1/10 | 1/10 | 1/5 | 0 | 0 | 1 | 110 |
1. В качестве базовой переменной можно выбрать x5.
2. В качестве базовой переменной можно выбрать x6.
3. В качестве базовой переменной можно выбрать x7.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (5,6,7).
Выразим базисные переменные через остальные:
x5 = -1/5x1-3/10x2-1/10x3-2/5x4+120
x6 = -2/5x1-1/10x2-3/10x3-1/5x4+150
x7 = -3/5x1-1/10x2-1/10x3-1/5x4+110
Подставим их в целевую функцию:
F(X) = 850x1+640x2+730x3+1000x4
1/5x1+3/10x2+1/10x3+2/5x4+x5=120
2/5x1+1/10x2+3/10x3+1/5x4+x6=150
3/5x1+1/10x2+1/10x3+1/5x4+x7=110
Введем новую переменную x0 = 850x1+640x2+730x3+1000x4.
Выразим базисные переменные <5, 6, 7> через небазисные (свободные).
x0 = 0+850x1+640x
2+730x3+1000x4
x5 = 120-1/5x1-3/10x2-1/10x3-2/5x4
x6 = 150-2/5x1-1/10x2-3/10x3-1/5x4
x7 = 110-3/5x1-1/10x2-1/10x3-1/5x4
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
Поскольку коэффициент при переменной x4 больше, чем при остальных переменных, то при увеличении x4 целевая функция будет увеличиваться быстрее.
max(850,640,730,1000,0,0,0) = 1000
x0 = 0+850x1+640x2+730x3+1000x4
x5 = 120-1/5x1-3/10x2-1/10x3-2/5x4
x6 = 150-2/5x1-1/10x2-3/10x3-1/5x4
x7 = 110-3/5x1-1/10x2-1/10x3-1/5x4
В качестве новой переменной выбираем x4.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai4 и из них выберем наименьшее:
min (120 : 2/5 , 150 : 1/5 , 110 : 1/5 ) = 300
Вместо переменной x5 в план войдет переменная x4.
Выразим переменную x4 через x5
x4 = 300-1/2x1-3/4x2-1/4x3-5/2x5
и подставим во все выражения.
x0 = 0+850x1+640x2+730x3+1000(300-1/2x1-3/4x2-1/4x3-5/2x5)
x6 = 150-2/5x1-1/10x2-3/10x3-1/5(300-1/2x1-3/4x2-1/4x3-5/2x5)
x7 = 110-3/5x1-1/10x2-1/10x3-1/5(300-1/2x1-3/4x2-1/4x3-5/2x5)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 300000+350x1-110x2+480x3-2500x5
x4 = 300-1/2x1-3/4x2-1/4x3-5/2x5
x6 = 90-3/10x1+1/20x2-1/4x3+1/2x5
x7 = 50-1/2x1+1/20x2-1/20x3+1/2x5
Полагая небазисные переменные x = (4, 6, 7) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-350, 110, -480, 0, 2500, 0, 0), x0 = 300000
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
Поскольку коэффициент при переменной x3 больше, чем при остальных переменных, то при увеличении x3 целевая функция будет увеличиваться быстрее.
max(350,-110,480,0,-2500,0,0) = 480
x0 = 300000+350x1-110x2+480x3-2500x5
x4 = 300-1/2x1-3/4x2-1/4x3-5/2x5
x6 = 90-3/10x1+1/20x2-1/4x3+1/2x5
x7 = 50-1/2x1+1/20x2-1/20x3+1/2x5
В качестве новой переменной выбираем x3.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3 и из них выберем наименьшее:
min (300 : 1/4 , 90 : 1/4 , 50 : 1/20 ) = 360
Вместо переменной x6 в план войдет переменная x3.
Выразим переменную x3 через x6
x3 = 360-6/5x1+1/5x2+2x5-4x6
и подставим во все выражения.
x0 = 300000+350x1-110x2+480(360-6/5x1+1/5x2+2x5-4x6)-2500x5
x4 = 300-1/2x1-3/4x2-1/4(360-6/5x1+1/5x2+2x5-4x6)-21/2x5
x7 = 50-1/2x1+1/20x2-1/20(360-6/5x1+1/5x2+2x5-4x6)+1/2x5
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 472800-226x1-14x2-1540x5-1920x6
x4 = 210-1/5x1-4/5x2-3x5+x6
x3 = 360-6/5x1+1/5x2+2x5-4x6
x7 = 32-11/25x1+1/25x2+2/5x5+1/5x6
Полагая небазисные переменные x = (4, 3, 7) равными нулю, получим новый допустимый вектор и значение целевой функции: