Задача линейного программирования. задача_ЛП_решение. Решение Занесём данные в распределительную таблицу Виды ресурсов
 Скачать 205.5 Kb.
|
|
Сформулировать задачу линейного программирования и решить ее симплекс-методом: Для изготовления трех видов продукции предприятие использует три разновидности ресурсов , запасы которых составляют 180; 120 и 220 единиц соответственно. Нормы расхода ресурса на единицу продукции первого вида составляют 9 единиц, на единицу продукции второго вида 9 единиц, на единицу продукции третьего вида 2 единицы. Соответствующие нормы для ресурса составляют 4 единицы, 3 единицы и 2 единицы, а для ресурса 1 единицу, 2 единицы и 4 единицы. Цена первого вида продукции равна 7 д. е., второго вида 8 д. е., третьего вида 6 д. е. Найти план производства, при котором достигается наибольшая стоимость произведенного продуктового набора. Решение: Занесём данные в распределительную таблицу:
Составим экономико-математическую модель задачи, для этого введём следующие обозначения: х1 – количество продукции I вида х2 – количество продукции II вида х3 – количество продукции III вида Тогда условия задачи выразятся в следующей системе неравенств:  При этом, исходя из экономического смысла задачи, х10, х2 0, х3 0 Целевая функция F= 7х1 + 8х2 + 6х3 стремится к максимуму. Будем решать задачу симплекс-методом. Приведём составленную задачу линейного программирования к каноническому виду. Для этого к каждому неравенству добавим неотрицательную переменную, всего добавить необходимо три переменных. Поскольку целевая функция F изначально стремится к максимуму, её не изменяем. Каноническая форма записи задачи линейного программирования: максимизировать функцию F= 7х1 + 8х2 + 6х3 при условиях:  В векторной форме задача выглядит таким образом: x1P1 + x2P2 + x3P3 + x4P4 + x5P5 + x6P6 =P0 В качестве базисных переменных возьмём х4, х5, х6, переменные х1, х2, х3 будут свободными.        Примем х1 = х2 = х3 = 0, в этом случае опорный план Х = (0; 0; 0; 180; 120; 220) = 0 Составим таблицу симплексного метода План 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как в этом столбце наибольший коэффициент по модулю в строке F. Вычислим по строкам как частное от деления: bi / ai2 и из них выберем наименьшее. После вычислений получаем, что первая строка (x4) является ведущей. Разрешающий элемент равен 9 и находится на пересечении ведущего столбца и ведущей строки. Переменная х2 становится базисной. Следовательно, замещается переменная х4. Составим вторую симплекс таблицу. Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=9 На месте разрешающего элемента в плане 1 получаем 1, в остальных клетках столбца x2 плана 1 записываются нули. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Расчет каждого элемента в таблице ниже:
Получаем новую симплекс-таблицу: План 1
В строке F имеются отрицательные элементы, следовательно, полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент – это  , соответствующий переменной x3. Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. После вычислений получаем, что ведущей строкой является x5, а разрешающий элемент равен  .Переменная х3 становится базисной. Следовательно, замещается переменная х5. Составим третью симплекс таблицу. Вместо переменной x5 в план 2 войдет переменная x3. Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ= На месте разрешающего элемента в плане 2 получаем 1, в остальных клетках столбца x3 плана 2 записываются нули. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Расчет каждого элемента в таблице ниже:
Получаем новую симплекс-таблицу: План 2
В строке F имеются отрицательные элементы, следовательно, полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент – это  , соответствующий переменной x4. Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. После вычислений получаем, что ведущей строкой является x6, а разрешающий элемент равен  .Переменная х4 становится базисной. Следовательно, замещается переменная х6. Составим третью симплекс таблицу. Вместо переменной x6 в план 3 войдет переменная x4. Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ= На месте разрешающего элемента в плане 3 получаем 1, в остальных клетках столбца x4 плана 3 записываются нули. Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника. Расчет каждого элемента в таблице ниже:
Получаем новую симплекс-таблицу: План 3
В строке F нет отрицательных элементов, следовательно, полуученое решение оптимально. Таким образом, опорный план: Х = (0; 5;  ; 30; 0;0)План оптимален F= 85 +70+ 6 = 355Из полученного оптимального плана следует, что производить продукцию вида II невыгодно. Следовательно, выгоднее всего поставить 5 единиц продукции вида I и  единиц продукции вида II. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
