Контрольная. Задача 37 b j a i запасы b 1 100
 Скачать 59.61 Kb.
|
1 2 Задание 2Симплекс-метод основан на последовательном приближении к оптимальности. Процедура симплекс-метода включает 3 существенных элемента: указывается способ нахождения исходного (опорного) плана; устанавливается признак, дающий возможность проверить, является ли допустимый план оптимальным; формулируются правила, по которым неоптимальный план можно улучшить. В математическую постановку задачи входит построение ограничений и целевой функции. Решение задачи линейного программирования симплекс-методом получается не аналитическим путем, т.е. не с помощью формул, позволяющих вычислить оптимальный план через ограничения и целевую функцию, что здесь и невозможно, а решение получается алгоритмически, шаг за шагом – итерационно. Особенность метода состоит в том, что составление первоначального плана основывается на понятии «базиса» – совокупности линейно независимых векторов. Таблица 2.1– Исходные данные
Решение Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 65x1+85x2+75x3 при следующих условиях-ограничений. 4,75x1+5,3x2+4,25x3≤3500 3,72x1+1,83x2+2,92x3≤1850 1,85x1+1,11x2+1,49x3≤1800 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. 4.75x1+5.3x2+4.25x3+x4 = 3500 3.72x1+1.83x2+2.92x3+x5 = 1850 1.85x1+1.11x2+1.49x3+x6 = 1800 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x4, x5, x6 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,3500,1850,1800) Базисное решение называется допустимым, если оно неотрицательно.
Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (3500 : 5,3 , 1850 : 1,83 , 1800 : 1,11 ) = 660,377 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (5.3) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=5.3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (5.3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (660,377 : 0,802 , 641,509 : 1,453 , 1066,981 : 0,6 ) = 441,644 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (1.453) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 2 войдет переменная x3. Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1.453. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Таким образом, в новом плане 2 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так: x1 = 0, x2 = 306,228, x3 = 441,644 F(X) = 65*0 + 85*306,228 + 75*441,644 = 59152,757 Анализ оптимального плана. В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 802.036. Значение 20.973> 0 в столбце x1 означает, что использование x1 - не выгодно. Значение 0 в столбце x2 означает, что использование x2 - выгодно. Значение 0 в столбце x3 означает, что использование x3 - выгодно. Значение 14.412 в столбце x4 означает, что теневая цена (двойственная оценка) равна y1=14.412. Значение 4.709 в столбце x5 означает, что теневая цена (двойственная оценка) равна y2=4.709. Значение 0 в столбце x6 означает, что теневая цена (двойственная оценка) равна y3=0. Список литературы1 2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||