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

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

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

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

Приведем систему к каноническому виду. Для этого введем балансовые переменные- х3, х4, х5 и получим модель в следующем виде:

3x1 +2х23 = 32

4x1 + 5х24= 48

x1 + 6х25= 40

хi≥0, i=1..5.

F= 6x1 + 11х2 →max.

Запишем данную задачу в исходную симплексную таблицу:

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5
     
х3
х4
х5
  F -6 -11

Первые три строки этой таблицы содержат в условной форме систему ограничений, а именно в столбце ai 0 - записываются свободные члены уравнений. В столбцах х1, х2, х3, х4, х5 – записываются коэффициенты при соответствующих переменных этой системы.

Слева от столбца ai0 , в столбце (хi), записываются базисные переменные (которые ввели для баланса), содержащиеся в соответствующих уравнениях системы. Верхняя строка и крайний верхний столбец содержат коэффициенты при соответствующих переменных в целевой функции.

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

а00 = 0∙32+0∙48+0∙40=0

Остальные значения обозначаются а0k , получаются в результате скалярного умножения вектора столбца Сi на вектор столбец коэффициента при неизвестном xk c последующим вычитанием соответствующего элемента верхней строки, например: а01=(0∙3+0∙4+0∙1)-6 = -6

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

1. выбираем в исходной таблице разрешающий столбец- p. Этот столбец соответствует наибольшей по абсолютной величине отрицательной оценке. В данной задаче это будет столбец х2 (т.к |-6| < |-11| ).

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

решение исходной задачи симплексным методом - student2.ru , т.е. 32/2=16, 48/5=9,6 , 40/6=6,66(min)

На перекрестке разрешающей строки и разрешающего столбца, получим разрешающий элемент - аqp. В данной задаче разрешающим элементом будет являться 6.

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5  
 
               
х3
х4
5

 
х5 q
  F -6 -11  
        p        

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

На месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы оценочной строки пересчитываем по формуле прямоугольников:

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

Расчет по формуле прямоугольников представлен в таблице

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5
х3 решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru
х4 решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru
х2 решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru
  F решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru

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

решение исходной задачи симплексным методом - student2.ru : решение исходной задачи симплексным методом - student2.ru =7

решение исходной задачи симплексным методом - student2.ru : решение исходной задачи симплексным методом - student2.ru = решение исходной задачи симплексным методом - student2.ru (min)

решение исходной задачи симплексным методом - student2.ru : решение исходной задачи симплексным методом - student2.ru = 40

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

Составляем новую таблицу - на месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы пересчитываем по формуле прямоугольников.

Получим таблицу

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5
х3 решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru
х1 решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru
х2 решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru
  F решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru решение исходной задачи симплексным методом - student2.ru

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

Оптимальное решение получаем в виде вектора xопт = (х1, х2, х3, х4, х5) Fmax = 92,63 Оптимальное решение к исходной задаче получается отбрасыванием из xопт компонент, связанными с балансовыми переменными х3, х4, х5, т.е xопт =( решение исходной задачи симплексным методом - student2.ru , решение исходной задачи симплексным методом - student2.ru ) Fmax = решение исходной задачи симплексным методом - student2.ru ∙6-11∙ решение исходной задачи симплексным методом - student2.ru = решение исходной задачи симплексным методом - student2.ru =92,63 Следовательно, фабрике необходимо выпускать решение исходной задачи симплексным методом - student2.ru единицы продукции вида А и решение исходной задачи симплексным методом - student2.ru единицы продукции вида В, при этом максимальная прибыль составляет 92,63 тысячи рублей.  

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