Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Определение ведущих столбца и строкиИз отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей интернации перейдет из свободных в базисные. Затем элементы столбца свободных членов симплексной таблицы делим на соответствующие только положительные элементы ведущего столбца. Результаты заносим в отдельный столбец . Строка симплексной таблицы. Соответствующая минимальному значению , является ведущей. Она определяет переменную , которая на следующей интерации выйдет из базиса и станет свободной. Элемент симплексной таблицы, находящейся на пересечении ведущих столбца и строки, называют разрешающими и выделяют кружком.
5. построение нового опорного плана. Переход к новому плану проводится перерасчетом симплексной таблицы по методу Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо в базис войдет переменная , соответствующая направляющему столбцу. Разделим все элементы ведущей строки предыдущей симплексной таблицы, соответствующую введенной в базис переменной . В результате этого на месте разрещающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника: НЭ=СТЭ- Где СТЭ – элемент старого плана, РЭ – разрешающий элемент, А и В – элементы старого плана, огбразующие прямоугольник с элементами СТЭ и РЭ.
6. полученный новый опорный план опять проверяется на оптимальность в соответствии с этапом 3 алгоритма. При решении задачи линейного программирования на минимум целевой функции, признаком оптимального плана является отрицательное значения всех коэффициентов индексной строки симплексной таблицы. Если в направляющем столбце все коэффициенты то функция цели неограниченна на множестве допустимых планов, т.е. и задачу решить нельзя. Если в столбце симплексной таблицы содержаться два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяющему завершить задачу. С целью исключения этого для выбора направляющей строки используют способ Креко, который заключается в следующем. Делим элементы строк, имеющие одинаковые наименьшее значение , на предполагаемые разрешающие элементы, а результаты заносим в дополнительные строки. За ведущую строку выбирается та, в которой раньше встречается меньшее число при чтении таблицы слева направо по столбцам. Если в оптимальный план вошла дополнительная переменная , то при реализации такого плана имеются недоиспользованные ресурсы i-го вида в количестве, полученном в столбце свободных членов симплексной таблицы. Если в индексной троке симплексной таблицы оптимального плана находиться нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧИ СИМЛЕКСНЫМ МЕТОДОМ.
Торговое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В, и С. Плановые нормативы затрат ресурсов на тыс. руб. товарооборота, прибыль от продажи товаров на тыс.руб. товарооборота, а ток же объем ресурсов заданы в таблице 2.
Определить плановый объем продажи и структуру товарооборота так, что бы прибыль торгового предприятия была максимальной.
Таблица 2.
1. запишем математическую модель задачи. Определить , который удовлетворяет условиям
И обеспечивают максимальное значение целевой функции
Для построения первого опорного плана систему неравенств привидем к системе уравнений.
В матрице этой системы уравнений имеет: Векторы А4,А5,А6 – линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля:
Соответствующие с этим векторам переменные х4,х5,х6 будут базисными. Решим систему уравнений относительно базисных переменных. Функционально запишем в виде:
Запишем первый опорный план в симплексную таблицу 3. Симплексная таблица 3.
3. первый опорный план 1 не оптимальный, так как в индексной строке находятся отрицательные коэффициенты -3,-4,-5. 4. за ведущий столбец выберем столбец, соответствующий переменной х2, так как сравнивая по модулю имеем:
Рассчитываем значения по строкам, как частное от деления И выбираем наименьшее: Следовательно, первая строка является ведущей. Элемент 0,2 находиться на пересечении ведущего столбца и ведущей строки и выделен.
Таким образом в новом плане II заполнены строки х2 и столбец х2. Все остальные элементы нового плана II, включая элементы индексной строки определяется по правилу прямоугольника. Для этого выбираем из старого плана 4 числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=0,2. Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции F(K1)=0=СЭ, которое указывает па место расположение нового НЭ в новом плане II. 'Третий элемент А=1100 и четвертый элемент В=-5 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения: НЭ=СЭ-(А*В)/РЭ=0 Элементы строки определяются аналогично:
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную. Выполняя последовательно все этапы алгоритма, формируем план II.
6 На третьей итерации таблицы 3 получаем план III, который является оптимальным так как все коэффициенты в индексной строке 0. Оптимальный план можно записать так: тыс. руб. Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В – 5375 ед. При этом торговое предприятие получает максимальную прибыль в размере 27625 тыс. руб. Товары группы С не реализуются. В оптимальном плане среди базисных переменных находится дополнительная переменная х6.Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м2, так как переменная х6 была введена в первое ограничение задачи, характеризующее собой использование этого ресурса. В индексной строке III плана в столбцах переменных х3,х4,х3, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным.
|