 ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса - ваш вокал Игровые автоматы с быстрым выводом Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Вкуснейший "Салат из свеклы с чесноком" Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Классификация ожирения по ИМТ (ВОЗ) Глава 3. Завет мужчины с женщиной
Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.
| Формализуем прямую задачу линейного программирования.
Обозначим: xj (jͼ3) шт. – количество товаров каждого вида, производимых предприятием в оптимальном плане Тогда ограничение задачи по использованию сырья S1 и S2 будут записаны соответственно: x1 + x2 + 5x3 ≤ 35 2x1 + x2 + 2x3 ≤ 20 x1 ≥0 x2≥0 х3≥0 C = 7x1 + 6x2 + 18x3 ® max Решим задачу симплекс-методом Приведем систему ограничений задачи к каноническому виду. Для этого введем в каждое ограничение задачи по одной дополнительной переменной. x1 + x2 + 5x3 + х4 ≤ 35 2x1 + x2 + 2x3 + х5 ≤ 20 x1 ≥0 x2≥0 х3≥0 х4≥0 х5≥0 В целевую функцию задачи дополнительные переменные вводятся с нулевыми коэффициентами. Далее необходимо найти опорный план задачи. Набор переменных х1, х2, …, xn, удовлетворяющий системе ограничений задачи, называется опорным планом. Опорных решений бесчисленное множество. Для нахождения опорного решения задачи необходимо основные искомые переменные приравнять к 0, тогда дополнительные переменные будут равны соответствующим свободным членам. Для нашей задачи
Иначе дополнительные переменные образуют базис задачи. Переменные, отличные от 0, в опорном решении задачи называются базисные переменные и обозначаются Бх. Для исследуемой задачи:
В некоторых случаях базис задачи бывает вырожденным. Это происходит тогда, когда одна или несколько дополнительных переменных равны 0. В любом случае, если дополнительная переменная равна 0, она все равно будет входить в базис задачи, при этом необходимо для дальнейшего решения задачи после нахождения опорного решения ликвидировать вырожденность. Для этого используют различные способы. После нахождения опорного решения переходят к нахождению оптимального плана задачи, используя метод последовательного улучшения плана или симплекс-метод. Эти методы используются чаще всего для решения прямых оптимизационных линейных задач. Симплекс-метод относится к методам с монотонным алгоритмом. Монотонность заключается в том, что при переходе от одного опорного плана к другому происходит улучшение качественного показателя или целевой функции задачи. Иначе, если задача решается на max, то при переходе от одной таблицы к другой значение целевой функции в последующей таблице не может быть меньше, чем в предыдущей, а на min – не может быть больше, чем в предыдущей. В алгоритме симплекс-метода используют принцип Жордана-Гаусса. Алгоритм симплекс-метода является классическим алгоритмом решения оптимизационных задач. Он лежит в основе целочисленного дробно-линейного и параметрического программирования. Рассмотрим алгоритм симплекс-метода. 1.На основе найденного опорного решения построим исходную симплексную таблицу, которая имеет вид:
2. Если задача решается на max, то технико-экономические коэффициенты заносят в С-строку (индексную строку) с противоположным знаком, а при решении на min, знаки не меняют. Рассматривая первую симплекс таблицу отмечают, что процесс производства товаров Т1, Т2 и Т3еще не начался, т.к. переменные х1 и х2, находящиеся в базисе задачи раны 0. Дополнительные переменные х4 и х5, обозначающие недоиспользованные ресурсы, здесь обозначают неиспользованные ресурсы. Если процесс производства товаров отсутствует, тогда значение прибыли (целевой функции) равно 0. 3. Если в индексной строке все коэффициенты не отрицательны, тогда оптимальный план найден. 4. Если в С-строке содержатся отрицательные коэффициенты, то план не оптимален, переходят к улучшению плана. 5.В индексной строке выбирают наибольший по модулю отрицательный коэффициент и столбец, его содержащий, считают разрешающим (ведущим) 6.Для нахождения разрешающей строки находят симплексные отношения (q). Отношение элементов столбца свободных членов bi к соответствующим элементам разрешающего столбца называют симплексными отношениями. 7. Если среди симплексных отношений встречаются нулевые отношения, то последнее определяет разрешающую строку в том случае, если в знаменателе этого отношения находится положительное число (например, 3/-5, 10/2, ,0/-4, 0/20). Например, среди записанных отношений 0/20 определяет разрешающую строку. Вообще наименьшее не отрицательное симплексное отношение определяет разрешающую строку. 8. Разрешающий элемент находится на пересечении найденных строки и столбца Далее переходят к расчету новой симплекс-таблицы, используя следующие правила: 1) Разрешающий элемент новой симплекс-таблицы всегда = 1. 2) Элементы разрешающего столбца всегда равны 0. 3) Элементы разрешающей строки находят путем деления каждого на разрешающий элемент. 4)Все остальные элементы, которые называются обыкновенными, рассчитывают по правилу прямоугольника. Обыкновенный элемент новой симплекс-таблицы равен дроби, в числителе которой стоит разность произведений элементов главной и побочной диагоналей прямоугольника, а в знаменателе – разрешающий элемент. Предприятие может производить 7 единиц товаров Т3 (х3=7) будет недоиспользоваться экономический ресурс S2 в размере 6 единиц (x5=6). Предприятие может получить 126 д.е. прибыли. Это второе опорное решение. Иначе такое решение называют промежуточным решением. Вновь переходят к улучшению плана, для этого рассчитывают таблицу 3. План не оптимален. В таблице 4 план оптимален, в С-строке отсутствует отрицательный коэффициент. Предприятие в оптимальном плане должно производить 5 единиц товара Т3 и 10 единиц товара Т2, при этом максимальная прибыль от производства составит 150 д.е.
|
