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

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

Проверяем начальное опорное решение на оптимальность. Индексная строка находится  по формуле Δ_к =∑С_бА_j-с_j. При решении задачи возможны следующие случаи:

1) при решении задачи на максимум:

а) все оценки Δ _к > О, тогда найденное решение оптимальное;

б) хотя   бы   одна   оценка  Δк < 0,   но   при   соответствующей   переменной   нет ни   одного положительного коэффициента, тогда решение задачи прекращаем, т.к. тах Z(Х) = ∞, т.е. целевая функция не ограничена в области допустимых решений;

в) хотя бы одна оценка   Δк < 0   и при соответствующей переменной есть  хотя бы  один

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

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

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

При решении задачи на максимум:

а) ключевым столбцом является столбец соответствующий наименьшей отрицательной оценке А_к в индексной строке;

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

столбца, т.е.

тiп Θ =                                  A₀

             {положит.эл.кл.столбца} 

в) ключевым элементом является число, расположенное на пересечении ключегого столбца и ключевой строки;

5.Заполняем  следующую симплексную таблицу.

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

б) заполняем базисные столбцы;

в) остальные коэффициенты таблицы находим по правилу «прямоугольника».

Правило «прямоугольника» заключается в следующем:

                                  соотв.эл.кл.столбца х соотв.эл.кл.строки

новый эл.=старый эл

                                              ключевойэлемент

Получаем  новое опорное решение.

6.Возвращаемся  к третьему шагу алгоритма. 

1.4. Решение задачи симплексным методом

      Предприятие изготавливает три вида станков I, II, III. При этом расходуются сырье, трудовые ресурсы и учитываются накладные расходы.

      Известно, что для изготовления станка I-го вида требуется по1 ед. сырья, трудовых ресурсов и накладных расходов; для станка II-го вида – 2 ед. сырья, 1 ед. трудовых ресурсов и 2 ед. накладных расходов; для станка III-го вида – 3 ед. сырья, 1 ед. трудовых ресурсов и 6 ед. накладных расходов. Предприятие может обеспечить 15 ед. сырья, 12 ед. трудовых ресурсов и 14 ед. накладных расходов. Прибыль от реализации станка I вида 5 тыс. руб., II вида – 9 тыс. руб., III вида – 8 тыс.руб.

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

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

Запишем условие задачи в виде таблицы: 

 

Составляем математическую модель задачи.

Вводим  переменные:

Пусть x₁; x₂; x₃ – количество станков каждого вида, причем х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0.

Составляем  систему ограничений:

S₁:1х₁+2х + 3х3≤15

Знак  “≤” ставим потому, что мы не можем использовать ресурсов больше, чем имеется в наличии.

S₂:1х₁+1х₂+1х₃=12

Знак  “=” ставим потому, что условие задачи требует, чтобы трудовые ресурсы были использованы полностью.

 S₃:1х₁+2х₂+6х₃≥14

Знак  “≥” ставим потому, что условие задачи требует, чтобы накладные расходы были не менее указанных.

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

Z(x)=5x₁+9x₂+8x₃ max

      Таким образом, математическая модель этой задачи имеет вид: найти такой план X=(х₁, х₂, ...,х_n) производства станков, удовлетворяющий стстеме ограничений:

хj≥0 (j=1,2,3), при  Z(x)=5x₁+9x₂+8x₃       max 

Приводим  задачу к канонической форме. Для  этого в систему ограничений  вводим дополнительные переменные, чтобы  уравнять правые и левые части: +x₄; -x₅. В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

Таким образом, каноническая форма задачи:

Z(x)=5x1+9x2+8x3+0x4+0x5  max

хj>=0 (j=1,2,3); 

 Z(x)=5x1+9x2+8x3+0x4+0x5        max

Строим начальное опорное решение методом Гаусса.

хj>=0 (j=1,2,3); 

 Z(x)=5x1+9x2+8x3+0x4+0x5         max 

+  

 
Домножим вторую строку матрицы  на (-1) и сложим ее с первой, а потом  с третьей.  В результате получим: 

+   

       

Домножим  вторую строку на (-5) и сложим ее со строкой  под чертой. В результате получим  : 

 +    
 

Домножим  третью строку на (-1) и сложим ее с первой, а потом со второй. В результате получим: 

+ 

Домножим  третью строку на -4 и сложим ее со строкой  под чертой. В результате получим  матрицу:

x1  x2    x3  x4   x5

0   0   -3   1   1    1  

1   0   -4   0   1    10

0   1    5   0   -1    2

0   0  -17  0    4    -68 

Составляем симплексную  таблицу. 

 

Проверяем решение на оптимальность, для этого вычисляем ∆_k: 

∆₀=   × -(-68)=68

∆₁=   × -0=0

∆₂ = × -0=0

∆₃= × -(-17)=17

  ∆₄= × - 0 = 0

 ∆₅= × -4=-4