Симплекс метод в линейном программировании

     

     

3.2 Основная идея  симплекс – метода

     Основная  идея симплекс – метода состоит  в следующем:

  Принимаются за базу одна из возможных программ – отправная (опорный план);

  Осуществляется  её пошаговое улучшение, пока не будет  достигнут оптимум по  заданной критерии функции.

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

     Решение задач симплекс – методом предусматривает  выполнение следующих процедур:

1)     Формирование целевой функции.

2)     Определение ограничительных условий – функциональных ограничений, которые могут иметь вид неравенств.

3)     Преобразование ограничений из неравенств в систему равенств путём ввода вспомогательных, свободных переменных (последние имеют экономическое содержание и характеризуют резерв, неиспользованный остаток тех ресурсов, по которым введено ограничение).

4)     Построение исходной симплексной таблицы – матрицы, в которой в формируемый план входят только свободные переменные.

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

6)     Определение числового значения вводимой переменной – величины программы.

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

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

1)    Значение столбцов, в которых в строке генерального элемента стоит ноль, переносится без изменения в новую матрицу.

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

 

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

4.1.Алгоритм  решения задачи  симплекс методом

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

1. Для получения начального решения выбираются m-переменных, которые называют базисными. Они обладают следующим свойством: входят с кооффициентом 1 только в одно уравнение. В оставшихся уравнениях коэффициент равен 0. Оставшиеся (m-n) переменные называются свободными. Все свободные члены полагаются равными нулю, а базисные равны соответствующим свободным членам. Находят начальное решение, как правило, являющееся допустимым.
2. Функцию f выражают через свободные переменные.
3. Проверка решения на оптимальность. Для этого просматривается целевая функция. Если коэффициенты при свободных переменных не отрицательны, то полученное решения является оптимальным. Если все эти коэффициенты положительны, полученное решение единственно. Если среди всех неотрицательных коэффициентов хотя бы один нулевой, то задача имеет бесконечное множество решений. Если в целевой функции присутствует хотя бы один отрицательный коэффициент, а в соответствующем столбце нет не одного положительного, то целевая функция неограниченна на области дополнительных решений. Если хотя бы один из коэффициентов при свободных переменных отрицательный, а в соответствующем ему столбце есть положительный коэффициент, то полученное решение может быть улучшено.
4. Получение нового решения. Выбор переменной, вводимой в список базисных переменных, осуществляется следующим образом: в целевой функции среди отрицательных элементов выбирается максимальный по абсолютной величине. Столбец, в котором расположен данный элемент называют разрешающим. Переменная, указанная в этом столбце, вводится в список базисных переменных. Далее определяется переменная, вводимая из списка базисных переменных. Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент, или на ноль, результат принимают за +беконечность. Среди данных отношений находят минимальное. Строка, которой соответствует минимальное отношение называется разрешающей. Базисная переменная, указанная в этой строке, выводится из списка базисных переменных. Элемент, который находится на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом после выполняются симплекс преобразования  и переход к новой системе решения (новая симплекс таблица). При переходе к новой симплекс таблице все элементы разрешающей строки делят на разрешающий элемент, а все оставшиеся элементы пересчитываются по следующей формуле: a_ij= (a_ij-a_ip*a_qj)/aqp, где aqp-разрешающий элемент.

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

     

     

4.2.Задача.

     Предприятие рекламирует свою продукцию с  использованием 4-х источников массовой информации: телевидение, радио, газеты, расклейка объявлений.

     Анализ  рекламной деятельности в прошлом  показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7, 7 у.е. в расчете на 1у.е. затраченную на рекламу. Всего на рекламу выделяют не более 50000 у.е. Администрация предприятия не намерена тратить на телевидении более 40 %, а на радио и газеты более 50 % от общей суммы. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль. 

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

Построение  математической модели.

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

  Цель  –максимизация прибыли.

2. Определяем параметры модели, т.е. заранее заранее фиксированные факторы.

  Параметры: все числовые данные, представленные в условии задачи.

3. Формируем управляющие переменные, изменяя значения которых приближаемся к поставленной цели. Значения управляющих переменных являются решениями задачи.

Управляющие переменные:  Х₁ –средства выделенные на телевидение

Х₂ –средства выделенные на радио

Х₃ –средства выделенные на газету

     Х₂ –средства выделенные на объявления

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

Х₁+Х₂+Х₃+Х₄ ≤ 50000

Область допустимых значений:       Х₁ ≤ 20000,

      Х₂+Х₃ ≤ 25000, Хj ≥ 0, j= 1,4

     (Рис.1.) 

f = 10X₁+5X₂+7X₃+4X₄           max

Решение:

Х₁+Х₂+Х₃+Х₄+Х₅=50000

Х₁+Х₆=20000

Х₂+Х₇=25000

Хj ≥ 0, j=1,7

f-10X₁-5X₂-7X₃-4X₄         max

X=(X₁=0, X₂=0, X₃=0, X₄=0, X₅=0, X₆=20000, X₇=25000)

 

 Min (50000/1; 20000/1; 25000/0)= 20000

(рис.2.) 

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

                                                               

(рис.3) 

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