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