Задачи линейного программирования

 

Оглавление

Введение

Глава 1. Теоретические основы

.1 Симплекс - метод

.2 Метод искусственного базиса

Глава 2. Практическая часть

Список литературы

Введение

Большинство управленческих задач обладает некоторыми особенностями. Первая из них заключается в том, что решения принимаются на основе информации. Иногда проблемы такого рода можно сформулировать (обычно после некоторых упрощений) таким образом, чтобы они решались с помощью математического метода, имеющего название линейного программирования.

Данная работа освещает один из способов решения задач линейного программирования (ЗЛП), а именно линейного программирования с вещественными числами симплекс-методом (конкретно - методом искусственного базиса).

Глава 1. Теоретические основы

.1 Симплекс - метод

Многие вопросы управления сводятся к тому, как распределить ограниченные ресурсы наилучшим образом. На языке математических моделей это означает, что мы хотим максимально увеличить (максимизировать) нечто (например, прибыль) или максимально уменьшить (минимизировать) нечто (например, стоимость). Обычно это нечто является функцией (которая известна как целевая функция) некоего числа факторов, называемых переменными. Этот процесс называют оптимизацией.

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

Общей задачей линейного программирования (ОЗЛП), заданной в произвольной форме записи, называют задачу, в которой требуется максимизировать (минимизировать) функцию

f =cj xj (1)

при условиях

a ij x j <= a i0 ( i = 1, …, s) (2)

a ij x j = a i0 ( i = s + 1, …, m) (3) j >=0 ( j= 1, …, t)

Существуют разные формы записи ЗЛП, но по теме задания нас интересует каноническая форма записи ЗЛП, так как именно к такой форме записи применим широко используемый симплекс-метод.

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

f =cj xj (4)

при условиях

a ij x j = a i0 ( i = 1, …, m) (5) j >=0 ( j= 1, …, n) (6)

Замечание: задачу минимизации f можно формально заменить задачей максимизации функции (-f).

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

1. Набор чисел Х = (x 1; …; x n), удовлетворяющий всем ограничениям задачи называется планом.
2. Набор чисел Х = (x 1; …; x n), называется опорным планом, если он соответствует крайней точке многогранника решений.
3. План Х = (x 1; …; x n), доставляющий функцию в экстремум называется оптимальным.

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

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

1. Ограничения вида «?»- ресурсные ограничения. Справа находится то, что мы используем на производстве, слева - то, что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0». Эти переменные несут определенный экономический смысл. Обычно они отражают недорасход ресурсов (остаток).
2. Ограничения вида «=». Часто бывает, несмотря на то, что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса. В систему ограничений они входят с коэффициентом «1», а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»). (Метод искусственного базиса).
3. Ограничения вида «?» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные как в предыдущем случае.

Решение ЗЛП наиболее рационально можно выполнять в табличной форме. Такие таблицы называются симплексными. В разной литературе построения симплекс таблиц немного отличаются друг от друга. Наиболее приемлемыми на мой взгляд являются таблицы, описанные в табл. 1.

Таблица 1

БПСП1-x m+1 …………….. - x m+s …………. -x nx 1 = x k = x m =b 11 …………………. b 1s ……………. b 1,n-m b k1 ……………………b ks ……………. b k,n-m b m1 …………………. b ms …………… b m,n-mb 10 b k0 b m0f =b 01 …………………. b0s …………….. b 0,n-mb 00

1.2 Метод искусственного базиса

Как уже говорилось выше, часто бывают проблемы с выделением единичного базиса. В таком случае предпочтительным является метод искусственного базиса. Наряду с исходной задачей, рассматривается расширенная задача, составленная на основе исходной, путем введения неотрицательных искусственных переменных, а из целевой функции вычтем сумму искусственных переменных, умноженную на сколь угодно большое положительное число М. В результате получим так называемую М-задачу.

F = cj xj - x n+i {max} (7)

a ij + x n+i = a i0 (i = 1, …, m) (8) j >=0 (j = 1, …, n+m) (9)

В системе (8) переменные x n+i (i = 1, …, m) образуют базис, называемый искусственным. При x 1= … = x n = 0 из (8) получаем начальный опорный план М-задачи: (0; …; 0; a 10; …; a m0).

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

1.Если в оптимальном плане М-задачи все искусственные переменные равны нулю (х 1; …; х n; 0; …; 0), то план (х 1; …; хn) является оптимальным для исходной задачи.

2.Если в оптимальном плане М-задачи по крайней мере одна из искусственных переменных положительна при любом большом М, то исходная задача не имеет ни одного плана.

.Если М-задача неразрешима, то и исходная задача неразрешима.

При решении ЗЛП методом искусственного базиса искусственные переменные следует вводить лишь в те уравнения, которые не разрешены относительно «естественных» базисных переменных.

Как видно из (7), целевая функция теперь содержит два слагаемых

cj xj и x n+i

поэтому в симплекс-таблицах для f отводят две строки (табл.1.3.) и признак оптимальности проверяется сначала по второй строке, отвечающей сумме

x n+i

Лишь после того, как все элементы этой строки станут равными нулю, признак оптимальности проверяют по первой строке, отвечающей сумме

cj xj

По мере исключения из базиса искусственных переменных соответствующие им столбцы опускают (не учитывают), так как искусственные переменные обратно в базис не вводятся.

Таблица 2

БПСП1-x m+1 …………….. - x m+s …………. -x nx 1 = x k = x m =b 11 …………………. b 1s ……… ……. b 1,n-m b k1 …………… ……b ks ………… …. b k,n-m b m1 …………………. b ms ………… … b m,n-mb 10 b k0 b m0Fb 01 …………………. b0s ………… ….. b 0,n-mb 00Мb 01(M) ………………. b0s(M) …………… b 0,n-m (M)b 00(M)

Глава 2. Практическая часть

Задача

Найти значения переменных ..., при которых функция:

линейный переменная функция симплекс искусственный

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

Ищем в системе ограничений базисные переменные.

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

Введем по одной искусственной неотрицательной переменной в каждое уравнение системы ограничений.

Получим следующую систему ограничений:

с базисными переменными .

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

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

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

вычтем из функции B уравнение 1

вычтем из функции B уравнение 2

вычтем из функции B уравнение 3

вычтем из функции B уравнение 4

Функция B примет вид:

Теперь мы можем сформировать начальную симплекс-таблицу.

БПРешениеОтношение3-33-6-21000002-13201006512-110010183-32-30000162L021410000-4B-113-67-10000-30

Итерация 1

БПРешениеОтношение1-11-2000002-132100606-390101800-13200162L02141000-4B0-85-15000-30

Итерация 2

БПРешениеОтношение1-10004020001000600010001002L02000-12B0-800000

Итерация 3

БПРешениеОтношение10004000010010000001023L0000-12B000000

Итерация 4

БПРешениеОтношение10041200000010000012L000-12B00000

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

Итерация 5

БПРешениеОтношение10041200000010000012L000-12

Итерация 6

БПРешениеОтношение3001200000010001016L-700-40

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Ответ: оптимальное значение функции достигается в точке с координатами: .

Список литературы

1. Глаголев А.А.., Солнцева Т.В. Курс высшей математики. Изд. 2-е, переработ. и доп. Учеб. пособие для вузов. - М.: Высш. школа, 1971.
2. Дегтярев Ю.И. Методы оптимизации: Учеб. пособие для вузов. - М.: Сов. радио, 1980.
3. Кузнецов А.В., Холод Н.И. Математическое программирование : Учеб. пособие для эконом. спец. вузов. - Мн.: Выш. школа, 1984.
4. Новые области применения математики. Под ред. Дж. Лайтхилла. Пер. с англ. А.Ф. Якубова. - Мн.: Выш. школа, 1981.

Оглавление Введение Глава 1. Теоретические основы .1 Симплекс - метод .2 Метод искусственного базиса Глава 2. Практическая часть Список ли

Больше работ по теме: