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

      Строим  ОДЗ для переменных задачи.

      По  этим  двум  точкам  строим  прямую.  Определяем,  какая  из  полуплоскостей  является  решением  данного  неравенства.  Для  этого  подставляем  координаты любой точки, не принадлежащей прямой, в первое неравенство. Для простоты вычислений возьмём точку (0;0). Получим: 2 × 0 – 0  ≤ 9. Такое неравенство является истинным и, следовательно, полуплоскость, на которой расположена точка (0;0), является искомой. 

      2.   – = 0   Данная прямая проходит через начало координат, поэтому  необходимо  взять  одну  точку  (0;0),  а  вторую  –  любую  другую,  удовлетворяющую данному уравнению. Например, точку (1;3).

      

      4.     ≥ 0 – это правая полуплоскость системы координат. 

      5.     ≥ 0 – это верхняя полуплоскость системы координат.

      Найдём  пересечение всех построенных полуплоскостей. Это будет многоугольник ABDE.

      Построим  направляющий вектор  = (1;3) и исходную изоцель. Сначала решаем задачу на нахождение максимального значения целевой функции. Для этого мысленно  перемещаем  изоцель в направлении  градиента  целевой  функции.  Она  станет  опорной  в  точке  D.  Решая  систему  из  двух  соответствующих уравнений, находим оптимальные значения переменных: D = = (8;7), = 29.

      Для решения задачи на нахождение минимального значения целевой функции перемещаем исходную изоцель в направлении противоположном градиенту целевой функции.. Изоцель станет опорной в точке (0;0). Таким образом,   = А = (0;0),   = 0.

 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение

      Таким образом в линейном программировании существует графический и симплексный методы решения задач, но Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж.Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения рассмотренного выше метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

      Симплекс-метод  основан на следующих свойствах задачи линейного программирования:

      Не  существует локального экстремума, отличного  от глобального. Другими словами, если экстремум есть, то он единственный. Множество всех планов задачи линейного  программирования выпукло. Целевая  функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек. Каждой угловой точке многогранника решений отвечает опорный план ЗЛП. 

Библиографический список

1.  Кузнецов  Ю.Н.  Математическое  программирование./Кузнецов  Ю.Н.,

Кузубов В.И., Волощенко  А.В – М.: Высш. шк., 1980. – 350 с.

2.  Акулич  И.Л. Математическое программирование  в примерах и зада-

чах: Учеб. пособие  для студентов экономических  специальностей вузов. – М.:

Высш. шк., 1986. – 319 с.

3.  Решение  задач математического программирования (курс лекций для 

студентов экономических специальностей) / Христиановский В.В., Ерин В.Г.,

Ткаченко О. В. – Донецк: ДонГУ, 1992. –254 с.

4.  Ходыкин В.Ф. Математическое программирование: Тексты лекций. –

донецк: ДонНу, 2000. – 76 с.

5.  Матряшин И.П. Математическое программирование./Матряшин И.П.,

Макеева В.К. –  М.: Высш. шк., 1978. – 160 с.

6.  Линейное и нелинейное программирование. / Под. Ред. И.Н. Ляшенко.

–Киев: Вища шк., 1975. – 372 с.

7.  Полунин И.В. Курс математического программирования. – Минск:

Вышэйш.. шк., 1970. – 320 с.

8.  Ларионов А.И. Экономико-математические методы в планирова-

нии./Ларионов А.И., Юрченко Т.И. – М.: Высш. шк., 1984. – 224 с.