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

Условие

Фирма производит и продает два вида товаров - чулки и носки. От продажи 1 пары чулок прибыль составляет 10 руб, и 4 руб от продажи 1 пары носков. Каждое изделие последовательно обрабатывается на 3-х технологических участках с затратами времени, приведенными в таблице

В следующем месяце фирма ежедневно будет располагать следующими ресурсами времени на каждом из участков - 60 ч на первом, 70 ч на втором и 100 ч на третьем.

Сколько производить продукции каждого вида чтобы прибыль была максимальной?

Теория

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

Теория симплексного метода: Симплексный метод является итерационным алгоритмом, основанным на последовательном перемещении от одной допустимой угловой точки (вершины) к другой с целью достижения оптимального решения. Он широко применяется благодаря своей эффективности на практике.

Основные шаги симплексного метода:

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

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

3. Выбор выходящей переменной (строки): Определение переменной, которая войдет в базис и улучшит текущее решение.

4. Пересчет таблицы: Обновление симплексной таблицы, чтобы отразить изменения в базисе переменных.

5. Проверка условия останова: Повторение шагов 2-4 до тех пор, пока не будет достигнуто оптимальное решение или определено, что решение неограничено.

Преимущества симплексного метода:

• Способен решать большие и сложные задачи линейного программирования.

• Эффективен в случае, когда решение существует в вершинах выпуклого многогранника.

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

Решение

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

     Определим максимальное значение целевой функции F(X) = 10x₁+4x₂ при следующих условиях-ограничениях:

      0,02x₁+0,01x₂≤60

      0,03x₁+0,01x₂≤70

      0,03x₁+0,02x₂≤100

     Для построения первого опорного плана  систему неравенств приведем к системе  уравнений путем введения дополнительных переменных (переход к канонической форме):

      0,02x₁ + 0,01x₂ + 1x₃ + 0x₄ + 0x₅ = 60

      0,03x₁ + 0,01x₂ + 0x₃ + 1x₄ + 0x₅ = 70

      0,03x₁ + 0,02x₂ + 0x₃ + 0x₄ + 1x₅ = 100

     Матрица коэффициентов A = a(ij) этой системы уравнений  имеет вид: 

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

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

     x₃, x₄, x₅,

     Полагая, что свободные переменные равны 0, получим первый опорный план:

     х₁ = (0,0,60,70,100)

  Переходим к основному алгоритму симплекс-метода

     Итерация  №0.

     Текущий опорный план неоптимален, так как  в индексной строке находятся  отрицательные коэффициенты

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

     Вычислим  значения D_i по строкам как частное от деления и из них выберем наименьшее: 

     Следовательно, 2-ая строка является ведущей:

      Формируем следующую часть симплексной таблицы. Вместо переменной х4 в план 1 войдет переменная х1. Получаем новую симплекс таблицу:

     Итерация  №1.

     Текущий опорный план неоптимален, так как  в индексной строке находятся  отрицательные коэффициенты

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

     Вычислим  значения D_i по строкам как частное от деления 

     и из них выберем наименьшее: 

     Следовательно, 3-ая строка является ведущей

      Формируем следующую часть симплексной таблицы. Вместо переменной х5 в план 2 войдет переменная х2. Получаем новую симплекс таблицу:

      Конец итераций: найден оптимальный план. Индексная строка не содержит отрицательных элементов.