Тема 6. Решение на задач линейного программирования на ПЭВМ

Симплекс-метод решения экономических задач оптимизации

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

Расширенная модель для рассматриваемой нами задачи имеет вид: Найти решение {x₁, x₂, x₃, x₄, x₅, x₆}, позволяющее максимизировать функцию прибыли

F = 2x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆

при условиях:

x₁ + 3x₂ + x₃ + 0x₄ + 0x₅ + 0x₆ = 18;

2x₁ + x₂ + 0x₃ + x₄ + 0x₅ + 0x₆ = 16;

0x₁ + x₂ + 0x₃ + 0x₄ + x₅ + 0x₆ = 5;

3x₁ + 0x₂ + 0x₁ + 0x₄ + 0x₅ + x₆ = 21.

Для решения оптимизационной задачи симплекс-методом следует составить исходную симплекс-таблицу (таблица 1) .

Таблица 1

Исходная симплекс-таблица

Составление первой симплекс-таблицы состоит в проверке выполнения критерия оптимальности и расчете оценочных отношений исходной симплекс-таблицы (см. табл.1).

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

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

Расчет оценочных отношений для каждой строки последнего столбца симплекс-таблицы производится по следующим правилам:

1) , если b_i и имеют разные знаки;

2) , если b_i = 0 и < 0;

3) , если = 0;

4) 0, если b_i =0 и > 0.

5) , если b_i и имеет одинаковые знаки, где - второй столбец.

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

После расчета оценочных отношений и определения разрешающего элемента формирование первой симплекс-таблицы завершено (см. табл.2)

Таблица 2

Первая симплекс-таблица

Затем переходят к составлению следующей (второй) симплекс-таблицы

Вторая симплекс-таблица (таблица 3) составляется на основе первой, соблюдая следующие правила:

а) в левом столбце записываем новый базис: вместо основной переменной - переменную ;

б) в столбцах, соответствующих основным переменным проставляем нули и единицы: 1 – против «своей» основной переменной, 0 – против «чужой» основной переменной , 0 – в последней строке против всех основных переменных;

в) новую строку с номером q получаем из старой делением на разрешающий элемент ;

г) все остальные элементы и вычисляем по правилу прямоугольника (рис. 1) с помощью формул

(5)

Рис. 1.

Проверка выполнения критерия оптимальности и расчета оценочных отношений во второй симплекс-таблице производится так же, как и в первой симплекс-таблице.

Таблица 3

Вторая симплекс-таблица (начало)

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

Таблица 4

Вторая симплекс-таблица (после завершения)

Аналогично составляются последующие симплекс-таблицы. В рассматриваемом примере требуется построить еще две таких таблиц. Они приведены в таблицах 5 и 6.

Таблица 5

Третья симплекс-таблица

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4	х5	х6
х1						-3
х4				-2				5/5←
х2								5/1
х6				-3				12/9
F						-3 ↑

Таблица 6

Четвертая симплекс таблица

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

х₁ = 6; х₂ = 4; х₅ = 1; х₆ = 3.

Значение показателя (F), принятого за критерий оптимальности, равно 24.

Решение совпадает с ранее полученным геометрическим методом.

6.2. Инструментарий «Поиск решения…» MS Excel и методика