• Document: МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  • Size: 896.03 KB
  • Uploaded: 2019-04-16 05:39:41
  • Status: Successfully converted


Some snippets from your converted document:

Глава 2 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 2.1. Симплекс-метод решения задачи линейного программирования Для решения задач линейного программирования симплекс- методом следует выполнить ряд подготовительных операций. 1. Привести задачу к каноническому виду. 2. Преобразовать систему ограничений (уравнений) к специ- альному виду, в котором переменные разделены на базисные и сво- бодные, а соответствующее базисное решение − неотрицательное (оно называется допустимым базисным решением или опорным решением). Пример такой системы: ⎧ x1 + a1 r +1 xr +1 + K + a1n xn = b1 , ⎪ ⎪ x2 + a2 r +1 xr +1 + K + a2 n xn = b2 , ⎨ (1) ⎪ . . . . . . . . . . . ⎪ xr + ar r +1 xr +1 + K + ar n xn = br , ⎩ где x1 , x2 ,K, xr – базисные переменные, xr +1 , xr +2 ,K, xn – свободные переменные bi ≥ 0, i = 1, 2,K , r. 3. Исключить из целевой функции базисные переменные с помощью (1) и записать ее в виде f + c r +1 xr +1 + ... + c n xn = c0 . (2) Коэффициенты ci , i = r + 1,K, n называются оценками соответ- ствующих переменных xr +1 , xr +2 ,K, xn . Из (1), (2) следует, что на допустимом базисном решении r xбаз = (c1 ; c2 ; K ; cr ; 0; 0; K ; 0) ∈ R n r целевая функция принимает значение f ( xбаз ) = c 0 . 24 После выполнения подготовительного этапа заполняется на- чальная симплекс-таблица: Б.н. С.ч. x1 … xr xr+1 … xp … xn x1 b1 1 … 0 a1 r+1 … a1 p … a1 n … … … … … … … … … … xq bq 0 … 0 aq r+1 … aq p … aq n bi/aip – min … … … … … … … … … … xr br 0 … 1 ar r+1 … ar p … ar n f c0 0 … 0 cr+1 … cp … cn Здесь и ниже используются следующие сокращения: 1. Б.н. – базисные неизвестные. 2. С.ч. – свободные члены. Таблица соответствует системе уравнений (1) с присоединен- ной целевой функцией (2). Последняя строка таблицы называется строкой оценок. Пусть решается задача о нахождении минимума функции f . Тогда цель дальнейших симплексных преобразований таблиц состо- ит в нахождении новых допустимых базисных решений, на которых значение целевой функции уменьшается (или не увеличивается). Алгоритм симплексных преобразований заключается в следующем. а) Если в строке оценок среди чисел ck (k ≠ 0) имеется хотя бы одна положительная (например cp), а в соответствующем столбце (разрешающем столбце) хотя бы один положительный элемент, то решение может быть улучшено. Среди указанных положительных элементов столбца в качестве разрешающего элемента aip выбира- ется тот, которому отвечает минимальное отношение bi/aip. Если имеется несколько элементов с подобным свойством, то в качестве разрешающего выбирается любой из них. В таблице таким элемен- том является aqp. Далее над таблицей проводятся элементарные преобразования: переменная xp становится базисной, а xq – свобод- ной. На новом базисном решении значение целевой функции не увеличивается, и с

Recently converted files (publicly available):