Симплексный метод решения задач линейного программирования

Методы решения задач линейного программирования

Графоаналитический метод

Свойства основной задачи линейного программирования связаны со свойствами выпуклых множеств.

Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию.

Геометрический смысл этого определения состоит в том, что множеству вместе с его произвольными точками полностью принадлежит и прямолинейный отрезок, который их соединяет. Примерами выпуклых множеств являются прямолинейный отрезок, полуплоскость, круг, шар, куб, полупространство и др.

Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой линейной комбинацией двух произвольных точек множества. Например, угловыми точками треугольника являются его вершины, круга – точки окружности, которая его ограничивает.

Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

Если основная задача линейного программирования имеет оптимальный план, то целевая функция задачи принимает экстремальное значение в одной из вершин многогранника решений. Если экстремальное значение достигается более чем в одной вершине, то целевая функция принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин.

Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник, каждая вершина которого определяет опорный план. Для одного из опорных планов (т.е. в одной из вершин многогранника решений) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов).

Вершину многогранника решений, в которой целевая функция принимает максимальное значение, можно найти достаточно просто, если задача в стандартной форме содержит не более двух переменных: Симплексный метод решения задач линейного программирования - student2.ru

при условиях Симплексный метод решения задач линейного программирования - student2.ru ,

Симплексный метод решения задач линейного программирования - student2.ru

Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость допустимых значений переменных соответственно с граничными прямыми

Симплексный метод решения задач линейного программирования - student2.ru .

Если система неравенств совместна, то областью допустимых решений задачи является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Решение задачи линейного программирования графоаналитическим методом включает следующие этапы.

1. На плоскости Симплексный метод решения задач линейного программирования - student2.ru строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Строят многоугольник решений.

4. Строят вектор-градиент целевой функции Симплексный метод решения задач линейного программирования - student2.ru , который указывает направление возрастания целевой функции. Координатами вектора Симплексный метод решения задач линейного программирования - student2.ru являются коэффициенты целевой функции при переменных Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru .

5. Строят линию уровня целевой функции, которая перпендикулярна вектору Симплексный метод решения задач линейного программирования - student2.ru и пересекает многоугольник решений, а затем передвигают ее в направлении вектора Симплексный метод решения задач линейного программирования - student2.ru до крайней угловой точки многоугольника решений, т.е. когда линия уровня примет положение опорной прямой. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если линия уровня целевой функции сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.

6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

7. Минимальное значение целевой функции находится путем передвижения линии уровня целевой функции в направлении, противоположном вектору Симплексный метод решения задач линейного программирования - student2.ru .

Пример 1.

Найдите экстремум линейной функции

Симплексный метод решения задач линейного программирования - student2.ru

при условиях-ограничениях:

Симплексный метод решения задач линейного программирования - student2.ru

Решение. Построим на плоскости Симплексный метод решения задач линейного программирования - student2.ru многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

Симплексный метод решения задач линейного программирования - student2.ru

Симплексный метод решения задач линейного программирования - student2.ru Построив прямые Симплексный метод решения задач линейного программирования - student2.ru , найдем соответствующие полуплоскости и их пересечение.

Направление стрелок от каждой граничной прямой определяется путем непосредственной подстановки в соответствующее неравенство координат произвольно взятой, так называемой контрольной точки, например (0; 0), и при удовлетворении данного неравенства направляем стрелки в сторону контрольной точки, в противном случае – наоборот.

Многоугольником решений задачи является пятиугольник Симплексный метод решения задач линейного программирования - student2.ru , координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи.

Для нахождения точек экстремума построим вектор Симплексный метод решения задач линейного программирования - student2.ru и линию уровня целевой функции Симплексный метод решения задач линейного программирования - student2.ru , которая перпендикулярна вектору Симплексный метод решения задач линейного программирования - student2.ru и пересекает пятиугольник Симплексный метод решения задач линейного программирования - student2.ru . Передвигая прямую Симплексный метод решения задач линейного программирования - student2.ru в направлении вектора Симплексный метод решения задач линейного программирования - student2.ru , найдем точку С, в которой линия уровня Симплексный метод решения задач линейного программирования - student2.ru принимает положение опорной прямой. Следовательно, в точке С целевая функция имеет максимальное значение. Так как точка С получена в результате пересечения прямых Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru , то ее координаты удовлетворяют уравнениям этих прямых:

Симплексный метод решения задач линейного программирования - student2.ru

Решив систему уравнений, получим: Симплексный метод решения задач линейного программирования - student2.ru , откуда найдем максимальное значение целевой функции:

Симплексный метод решения задач линейного программирования - student2.ru .

По условию задачи линии уровня целевой функции параллельны прямой Симплексный метод решения задач линейного программирования - student2.ru , т.к. коэффициенты при переменных Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru пропорциональны: Симплексный метод решения задач линейного программирования - student2.ru .

Следовательно, линия уровня Симплексный метод решения задач линейного программирования - student2.ru займет положение опорной прямой в точке В, С и в любой точке отрезка ВС, в которых целевая функция Симплексный метод решения задач линейного программирования - student2.ru принимает одно и то же максимальное значение. Для определения координат точки В решим систему двух линейных уравнений:

Симплексный метод решения задач линейного программирования - student2.ru

Максимальное значение целевой функции в точке В равно:

Симплексный метод решения задач линейного программирования - student2.ru .

Запишем множество оптимальных решений как выпуклую комбинацию угловых точек В и С:

Симплексный метод решения задач линейного программирования - student2.ru где Симплексный метод решения задач линейного программирования - student2.ru .

Подставив координаты угловых точек, получим:

Симплексный метод решения задач линейного программирования - student2.ru

Тогда Симплексный метод решения задач линейного программирования - student2.ru , где Симплексный метод решения задач линейного программирования - student2.ru .

Подставляя любые значения Симплексный метод решения задач линейного программирования - student2.ru от 0 до 1, получим координаты множества точек отрезка ВС, в каждой из которых целевая функция принимает максимальное значение, равное 10.

Для нахождения минимального значения целевой функции задачи перемещаем линию уровня Симплексный метод решения задач линейного программирования - student2.ru в направлении, противоположном вектору Симплексный метод решения задач линейного программирования - student2.ru . Линия уровня Симплексный метод решения задач линейного программирования - student2.ru займет положение опорной прямой в вершине Симплексный метод решения задач линейного программирования - student2.ru , где Симплексный метод решения задач линейного программирования - student2.ru , а минимальное значение целевой функции равно:

Симплексный метод решения задач линейного программирования - student2.ru .

Пример 2.В качестве второго примера на применение графоаналитического метода к решению задачи линейного программирования рассмотрим задачу, модель которой была приведена в качестве примера в разделе 1.1.

Построим на плоскости Симплексный метод решения задач линейного программирования - student2.ru многоугольник решений задачи. Для этого в неравенствах системы ограничений

Симплексный метод решения задач линейного программирования - student2.ru

знаки неравенств заменим на знаки точных равенств:

Симплексный метод решения задач линейного программирования - student2.ru

Построив полученные граничные прямые, найдем соответствующие полуплоскости допустимых значений переменных и их пересечение.

Симплексный метод решения задач линейного программирования - student2.ru

Симплексный метод решения задач линейного программирования - student2.ru
Аналогично предыдущему примеру получаем многоугольник решений задачи, которым является шестиугольник Симплексный метод решения задач линейного программирования - student2.ru .

Далее строим вектор-градиент Симплексный метод решения задач линейного программирования - student2.ru и линию уровня целевой функции Симплексный метод решения задач линейного программирования - student2.ru , которая перпендикулярна вектору Симплексный метод решения задач линейного программирования - student2.ru и пересекает шестиугольник Симплексный метод решения задач линейного программирования - student2.ru . Поскольку нас интересует максимальное значение целевой функции, то передвигая линию уровня Симплексный метод решения задач линейного программирования - student2.ru в направлении вектора Симплексный метод решения задач линейного программирования - student2.ru , найдем точку Е, в которой линия уровня Симплексный метод решения задач линейного программирования - student2.ru принимает положение опорной прямой. Следовательно, в точке Е целевая функция имеет максимальное значение. Так как точка Е получена в результате пересечения прямых Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru , то для определения ее координат решим систему уравнений:

Симплексный метод решения задач линейного программирования - student2.ru

Максимальное значение целевой функции

Симплексный метод решения задач линейного программирования - student2.ru (тыс. руб.)

Таким образом, суточный объем производства краски для наружных работ должен быть равен Симплексный метод решения задач линейного программирования - student2.ru т, а для внутренних работ – Симплексный метод решения задач линейного программирования - student2.ru т. Доход от продажи в этом случае будет максимальным и составит Симплексный метод решения задач линейного программирования - student2.ru тыс. руб.

Симплексный метод решения задач линейного программирования

Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.

Симплексный метод – это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, в частности по угловым точкам многоугольника решений, полученного графоаналитическим методом.

В тех случаях, когда модель содержит т уравнений в основной системе ограничений, для построения пробных решений используется т переменных, принимающих некоторые положительные значения при нулевых значениях остальных переменных. Вначале предположим, что решение существует, причем оптимальное значение целевой функции конечно. В этом случае вычислительная процедура может быть представлена в следующей последовательности.

1.Выбираем т переменных, задающих допустимое пробное решение, и исключим эти переменные из целевой функции.

2.Проверим, нельзя ли за счет одной из переменных, приравненной вначале к нулю, улучшить значение целевой функции, придавая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к третьему пункту, в противном случае прекратим вычисления.

3.Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из выражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.

4.Разрешим систему т уравнений относительно переменной, вошедшей в новое пробное решение. Исключим эту переменную из выражения для целевой функции. Вернемся ко второму пункту.

Важно отметить, что предложенный алгоритм действительно приводит к оптимальному решению для любой модели линейного программирования за конечное число итераций, если система ограничений задачи совместна и оптимальное значение целевой функции конечно.

Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции улучшается. Рассмотрим алгоритм симплексного метода на примере задачи рационального использования ресурсов.

Предприятие изготовляет п видов продукции, расходуя на это т видов сырья, запасы которых известны Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru ). Прибыль, получаемая от реализации единицы каждого вида продукции, Симплексный метод решения задач линейного программирования - student2.ru . Нормативы затрат сырья на изготовление единицы продукции составляют Симплексный метод решения задач линейного программирования - student2.ru .

Необходимо составить такой план выпуска продукции, при котором прибыль от ее реализации будет максимальной.

Математическую модель задачи запишем следующим образом.

Определить план Симплексный метод решения задач линейного программирования - student2.ru , который удовлетворяет ограничениям

Симплексный метод решения задач линейного программирования - student2.ru

и обеспечивает максимальное значение целевой функции Симплексный метод решения задач линейного программирования - student2.ru .

Алгоритм симплексного метода включает следующие этапы.

1. Составление начального опорного плана.

Система ограничений решаемой задачи задана в виде неравенств смысла Симплексный метод решения задач линейного программирования - student2.ru , правые части которых Симплексный метод решения задач линейного программирования - student2.ru . Перейдем от системы неравенств к системе уравнений путем введения дополнительных неотрицательных переменных, каждая из которых определяет объем соответствующего неиспользованного ресурса. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными:

Симплексный метод решения задач линейного программирования - student2.ru ,

где Симплексный метод решения задач линейного программирования - student2.ru базисные переменные, Симплексный метод решения задач линейного программирования - student2.ru

Симплексный метод решения задач линейного программирования - student2.ru свободные переменные, Симплексный метод решения задач линейного программирования - student2.ru

Решим эту систему относительно базисных переменных:

Симплексный метод решения задач линейного программирования - student2.ru ,

а функцию цели перепишем в виде уравнения

Симплексный метод решения задач линейного программирования - student2.ru

Дополнительные переменные вошли в выражение целевой функции с нулевыми коэффициентами, поскольку неиспользованные ресурсы прибыли не дают.

Полагая, что основные переменные Симплексный метод решения задач линейного программирования - student2.ru , получим начальный опорный план Симплексный метод решения задач линейного программирования - student2.ru , и соответствующее этому плану значение целевой функции Симплексный метод решения задач линейного программирования - student2.ru , что соответствует действительному положению дел, продукция не производится, ресурсы не используются, реализации и прибыли нет из-за отсутствия продукции.

Реализация симплексного метода при решении задач линейного программирования осуществляется с помощью симплексных таблиц. В таблице выписаны соответствующие векторы Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru . Вектор Симплексный метод решения задач линейного программирования - student2.ru составлен из свободных членов системы основных ограничений. Среди соответствующих векторов есть т векторов, образующих базис. Их записывают в колонку «Б». Как видим, полагая свободные переменные равными нулю, из таблицы можно получить начальный опорный план задачи.

В таблице также записываются коэффициенты при переменных в целевой функции (первая строка), коэффициенты при базисных переменных в целевой функции (колонка Симплексный метод решения задач линейного программирования - student2.ru ). Строка Симплексный метод решения задач линейного программирования - student2.ru называется индексной или строкой оценок. В ней расположены оценки векторов, которые рассчитываются так: находят сумму произведений компонент вектора на элементы колонки Симплексный метод решения задач линейного программирования - student2.ru и вычитают из полученного числа коэффициент при соответствующей переменной в целевой функции. Эти числа показывают, на сколько изменится значение целевой функции, если соответствующая переменная возрастет на единицу.

Оценка вектора Симплексный метод решения задач линейного программирования - student2.ru число, стоящее на пересечении индексной строки и колонки Симплексный метод решения задач линейного программирования - student2.ru , показывает значение целевой функции плана, записанного в данной таблице. Оно находится как сумма произведений элементов столбца Симплексный метод решения задач линейного программирования - student2.ru на компоненты вектора Симплексный метод решения задач линейного программирования - student2.ru .

Оценки векторов используются для проверки оптимальности плана.

2. Проверка плана на оптимальность.

Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны Симплексный метод решения задач линейного программирования - student2.ru , то план является оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план неоптимальный и его можно улучшить. В этом случае переходим к следующему этапу алгоритма.

3. Определение ключевого столбца и строки.

Из отрицательных коэффициентов индексной строки выбираем тот, который позволяет наибольшим образом изменить значение целевой функции. Он и определяет ключевой столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные и какой вектор войдет в базис.

Затем элементы столбца свободных членов симплексной таблицы делим на положительные элементы ключевого столбца. Результаты заносим в отдельный столбец Симплексный метод решения задач линейного программирования - student2.ru . Строка симплексной таблицы, соответствующая минимальному значению Симплексный метод решения задач линейного программирования - student2.ru , является ключевой. Она определяет вектор, который на следующей итерации выйдет из базиса.

Элемент симплексной таблицы, находящийся на пересечении ключевого столбца и строки, называют ключевым и выделяют кружком.

4. Построение нового опорного плана.

Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим векторы в базисе, т.е. вместо Симплексный метод решения задач линейного программирования - student2.ru в базис войдет Симплексный метод решения задач линейного программирования - student2.ru , соответствующий ключевому столбцу.

Разделим все элементы ключевой строки предыдущей симплексной таблицы на ключевой элемент и результаты деления запишем в строку следующей симплексной таблицы, соответствующую введенному в базис вектору Симплексный метод решения задач линейного программирования - student2.ru . В результате этого, на месте ключевого элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках Симплексный метод решения задач линейного программирования - student2.ru го столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:

Симплексный метод решения задач линейного программирования - student2.ru ,

где Симплексный метод решения задач линейного программирования - student2.ru элемент старого плана, Симплексный метод решения задач линейного программирования - student2.ru ключевой элемент, Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru элементы старого плана, образующие прямоугольник с элементами Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru .

Затем возвращаемся ко второму этапу алгоритма – проверке нового плана на оптимальность.

Замечание 1. При решении задачи линейного программирования на минимум целевой функции признаком оптимальности плана являются неположительные значения всех коэффициентов индексной строки симплексной таблицы.

Замечание 2. Если в ключевом столбце все коэффициенты Симплексный метод решения задач линейного программирования - student2.ru , то функция цели неограничена на множестве допустимых планов, т.е. Симплексный метод решения задач линейного программирования - student2.ru и задача не имеет решения (в случае исследования Симплексный метод решения задач линейного программирования - student2.ru на Симплексный метод решения задач линейного программирования - student2.ru ).

Замечание 3. Если в столбце Симплексный метод решения задач линейного программирования - student2.ru симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. С целью исключения этого для выбора ключевой строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие Симплексный метод решения задач линейного программирования - student2.ru , делятся на предполагаемые ключевые элементы, а результаты заносятся в дополнительные строки. В качестве ключевой строки выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содержащая три равных значения Симплексный метод решения задач линейного программирования - student2.ru , имеет следующий вид:

Б Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru 4 : 2 = 2
Симплексный метод решения задач линейного программирования - student2.ru 8 : 4 = 2
Симплексный метод решения задач линейного программирования - student2.ru -1 10 : 5 = 2

Допустим, ключевым столбцом является Симплексный метод решения задач линейного программирования - student2.ru , который вводится в новый план. Тогда ключевым элементом может быть: 2, 4 или 5. Следуя указанному правилу, получаем таблицу:

Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
1,5 0,5
0,25 0,25
2,4 -0,2 0,2 0,2

Сравниваем последовательно слева направо полученные частные по столбцам. В первом и втором столбце все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в первой строке, следовательно, эта строка и будет ключевой с ключевым элементом 2.

Замечание 4. Если в оптимальный план вошла дополнительная переменная Симплексный метод решения задач линейного программирования - student2.ru , то при реализации такого плана имеются неиспользованные ресурсы Симплексный метод решения задач линейного программирования - student2.ru го вида, полученном в столбце свободных членов симплексной таблицы.

Замечание 5. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий вектору, не вошедшему в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет бесчисленное множество оптимальных планов. Вектор, соответствующий указанному столбцу, можно ввести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.

Пример.

Предприятие выпускает три вида продукции: А, В, С, используя при этом три вида ресурсов: Симплексный метод решения задач линейного программирования - student2.ru . Известны удельные расходы ресурсов, их запасы и прибыль, получаемая от реализации единицы продукции. Указанные данные размещены в таблице.

Необходимо определить какое количество продукции соответствующего вида должно изготовить предприятие из имеющихся ресурсов, чтобы, реализовав изготовленную продукцию, получить максимальную прибыль.

Ресурсы А В С Запас
Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru
Прибыль  

Решение. Запишем математическую модель задачи.

Определим план Симплексный метод решения задач линейного программирования - student2.ru , который удовлетворяет условиям

Симплексный метод решения задач линейного программирования - student2.ru

и обеспечивает максимальное значение целевой функции

Симплексный метод решения задач линейного программирования - student2.ru .

Для построения начального опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных неотрицательных переменных Симплексный метод решения задач линейного программирования - student2.ru :

Симплексный метод решения задач линейного программирования - student2.ru

Очевидно, что переменные Симплексный метод решения задач линейного программирования - student2.ru в этой системе являются базисными, а Симплексный метод решения задач линейного программирования - student2.ru свободными.

Следует отметить, что смысл переменных Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru неиспользованные ресурсы вида Симплексный метод решения задач линейного программирования - student2.ru соответственно и поэтому эти переменные войдут в выражение целевой функции с нулевыми коэффициентами:

Симплексный метод решения задач линейного программирования - student2.ru

Полагая, что свободные переменные Симплексный метод решения задач линейного программирования - student2.ru , получим начальный опорный план Симплексный метод решения задач линейного программирования - student2.ru , в котором базисные переменные Симплексный метод решения задач линейного программирования - student2.ru . Следовательно, продукция не изготовляется и не реализуется, ресурсы не используются, а прибыль равна нулю. Полученный начальный опорный план запишем в симплексную таблицу.

Симплексный метод решения задач линейного программирования - student2.ru Б Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru -12 -9 -14 Симплексный метод решения задач линейного программирования - student2.ru -240 -560

Начальный опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: Симплексный метод решения задач линейного программирования - student2.ru .

Учитывая экономический смысл элементов индексной строки, за ключевой столбец выбираем столбец Симплексный метод решения задач линейного программирования - student2.ru , а затем по наименьшему элементу столбца Симплексный метод решения задач линейного программирования - student2.ru за ключевую строку – первую строку.

Ключевой элемент равен 5 и находится на пересечении ключевого столбца и ключевой строки и выделен в таблице.

Формируем следующую симплексную таблицу. Вместо вектора Симплексный метод решения задач линейного программирования - student2.ru в базис войдет вектор Симплексный метод решения задач линейного программирования - student2.ru . Первая строка в этой таблице получена в результате деления всех элементов первой строки первой симплексной таблицы на ключевой элемент Симплексный метод решения задач линейного программирования - student2.ru . На месте ключевого элемента во второй таблице получаем 1. В остальных клетках столбца Симплексный метод решения задач линейного программирования - student2.ru второй таблицы записываем нули. Столбцы Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru переносятся во вторую симплексную таблицу без изменения, т.к. они остались в базисе.

Таким образом, во второй симплексной таблице заполнены первая строка и столбцы Симплексный метод решения задач линейного программирования - student2.ru , Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru . Все остальные элементы второй симплексной таблицы, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из первой таблицы четыре числа, которые расположены в вершинах прямоугольника и всегда включают ключевой элемент Симплексный метод решения задач линейного программирования - student2.ru . Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции Симплексный метод решения задач линейного программирования - student2.ru , которое указывает на место расположения нового элемента Симплексный метод решения задач линейного программирования - student2.ru во второй симплексной таблице. Третий элемент Симплексный метод решения задач линейного программирования - student2.ru и четвертый элемент Симплексный метод решения задач линейного программирования - student2.ru завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента во второй симплексной таблице находится из выражения:

Симплексный метод решения задач линейного программирования - student2.ru .

Элементы второй строки определяются аналогично:

Симплексный метод решения задач линейного программирования - student2.ru

Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.

Симплексный метод решения задач линейного программирования - student2.ru Б Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru -1
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru -32

Контроль. Из второй симплексной таблицы можно выписать план рассматриваемой задачи Симплексный метод решения задач линейного программирования - student2.ru и значение целевой функции на нем Симплексный метод решения задач линейного программирования - student2.ru .

Полученный план неоптимальный, поскольку в индексной строке находится отрицательный коэффициент: Симплексный метод решения задач линейного программирования - student2.ru .

На третьей итерации (третья симплексная таблица) получаем план, который является оптимальным, т.к. все коэффициенты в индексной строке Симплексный метод решения задач линейного программирования - student2.ru .

Симплексный метод решения задач линейного программирования - student2.ru Б Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru
Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru Симплексный метод решения задач линейного программирования - student2.ru

Оптимальный план можно записать так: Симплексный метод решения задач линейного программирования - student2.ru .

Следовательно, предприятие для получения максимальной прибыли в размере 592 денежных единицы должно из имеющихся ресурсов изготовить и реализовать 40 единиц продукции вида А и 8 единиц продукции вида С, а продукцию вида В совсем не производить. При этом ресурсы Симплексный метод решения задач линейного программирования - student2.ru и Симплексный метод решения задач линейного программирования - student2.ru будут использованы полностью, а ресурс Симплексный метод решения задач линейного программирования - student2.ru останется в количестве 12 единиц.

В индексной строке последней симплексной таблицы небазисные столбцы имеют ненулевые оценки, поэтому полученный оптимальный план является единственным.

Наши рекомендации