Задачи линейного программирования. _Готовое 84-04-3. Задача 1 3 Задача 2 6 Задача 3 9 Задача 4 15
 Скачать 109.17 Kb.
|
Задача 3Изготовление двух изделий А и В требует три вида сырья. На производство единицы изделия А требуется затратить сырья: первого вида 1 кг; сырья второго вида 4 кг; сырья третьего вида 4 кг. На производство единицы изделия В требуется затратить сырья: первого вида 5 кг; сырья второго вида 3 кг; сырья третьего вида 1 кг. Производство обеспечено сырьем первого вида в количестве 25 кг, сырьем второго вида в количестве 32 кг, сырьем третьего вида в количестве 28 кг. Прибыль от реализации единицы готового изделия А составляет 11 ус. ед., а изделия В – 15 ус. ед. Составьте план производства обоих изделий, обеспечивающий максимальную прибыль. Решение: Сначала перепишем условие задачи в виде таблицы 4. Обозначим через  количество продукции вида A и B соответственно. Тогда целевую функцию можно записать следующим образом: .Таблица 4
Используя таблицу 4, составим систему ограничений: x  1+5x2≤254x1+3x2≤32 4x1+x2≤28 x1≥0, x2≥0 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В  1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.x1+5x2+x3 = 25 4x1+3x2+x4 = 32 4x1+x2+x5 = 28 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x3, x4, x5 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,25,32,28) Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (25 : 5 , 32 : 3 , 28 : 1 ) = 5 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (5 : 1/5 , 17 : 32/5 , 23 : 34/5 ) = 5 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (32/5) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=32/5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так: x1 = 5, x2 = 4 При данном плане производства максимальная прибыль составит: F(X) = 11*5 + 15*4 = 115 ус. ед. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||