Главная › Интернет › Какой столбец симплекс таблицы называется ведущим. Пример решения прямой и двойственной задачи симплекс методом. Преобразование разрешающего элемента

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

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

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

Q =

x 1

x 2

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

x 1

x 2

x 3

(1)

x 1

x 2

x 4

(2)

x 2

x 5

(3)

x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

Симплекс таблица имеет следующий вид:

БП

x 1

x 2

x 3

x 4

x 5

Решение

Отношение

x 3

x 4

x 5

-1

-2

Самая верхняя строка - чисто информационная, в ней указывается назначение столбцов. Столбец "БП" также информационный, каждая клетка этого столбца содержит имя переменной, являющейся в соответствующем уравнении системы ограничений. В нашем примере, в первом уравнении, переменная X 3 , во втором X 4 , в третьем X 5 .

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

Коэффициенты целевой функции отражаются в симплекс-таблице в строке "Q", свободный член, как и в случае с уравнениями системы ограничений, изначально записывается в столбец "Решение". Он же одновременно является значением целевой функции, но записанный с противоположным знаком (это удобно для симплекс-метода). В нашем примере показанная симплекс-таблица соответствует некоторому решению при котором переменные X 3 , X 4 , X 5 равны соответственно 64, 70, 18 (см. столбец "Решение"), а остальные перемнные равны нулю. Значение целевой функции "Q" при этом равно двум (что несложно проверить подставив значения переменных в выражение для целевой функции).

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

Строка "Q" в данном примере выделена желтым цветом, это значит, что по ней будет приниматься решение относительно выбора разрешающего столбца (иногда его называют направляющим). Разрешающий столбец соответствует переменной, которая будет введена в базис (в список) на следующей итерации решения задачи. Цель подобной замены базиса - улучшение значения целевой функции. Критерием выбора разрешающего столбца является максимальный положительный коэффициент в строке "Q", при решении задачи на максимум, или минимальный отрицательный, при решении задачи на минимум. Если после очередной итерации в строке не окажется положительных (при максимизации), или отрицательных (при минимизации) коэффициентов, то оптимальное решение достигнуто. В нашем примере разрешающий столбец выбран по коэффициенту 7 (максимальный положительный т.к. задача на максимум), он соответствует переменной X 2 , именно она будет введена в базис на следующей итерации. Числа стоящие в направляющем столбце окрашиваются красным цветом.

Красным цветом также окрашивается и разрешающая (направляющая) строка, она соответствует переменной которая будет выведена из базиса (списка) на следующей итерации. Для ее определения рассчитывается и заполняется столбец "Отношение". Его элементы представляют собой отношения элементов столбца "Решение" к соответсвующим элементам направляющего столбца (кроме строки "Q"). Выбор разрешающей строки производится по минимальному значению из всех отношений. Важно то, что данные отношения рассчитываются только для положительных элементов направляющего столбца. Если на некоторой итерации в направляющем столбце положительных коэффициентов не окажется, то целевая функция исходной задачи неограничена, задача не имеет решения.
В нашем примере направляющая строка выбрана по минимальному отношению 16, она соответствует X 3 , именно она будет выведена из базиса на следующей итерации (ее место займет X 2).

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

Первая строка, в отличие от столбца, сохраняется лишь в первой симплексной таблице. Начиная со второй итерации верхняя строка перестает быть обязательной.

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

Второй столбец – р k (индеек k – номер итерации).

В этом столбце указываются номера неизвестных, входящих в базисное решение. Эти номера используют для нумерации соответствующих строк матрицы.

В первой симплексной таблице в столбце р 0 указываются номера всех дополнительных переменных.

3. Третий столбец – х 0 .

В первой симплексной таблице он заполняется свободными членами уравнений из системы ограничений. В процессе итеративного расчета эти показатели преобразуются в искомое решение. Поэтому данный столбец носит название итогового столбца .

4. Значение целевой функции F k .

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

Столбцы «основания матрицы».

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

В этих столбцах в первой симплексной таблице приводятся коэффициенты при неизвестных из уравнений исходных условий.

6. Последующие три столбца таблицы (, , ) имеют вспомогательное значения. Без этих столбцов можно обойтись, но они существенно облегчают проведение расчетов. Более подробно содержание этих столбцов будет рассматриваться ниже.

Пример

Рассмотрим симплексную задачу, записанную в общем виде:

Приведем задачу к канонической форме. Для этого в каждое из неравенств системы введем по одному неизвестному (дополнительному) – х 4 , х 5 . х 6 . Тогда

F = 15x 1 + 20x 2 +5x 3  max.

Заполним первую симплексную таблицу.

Мы заполним все клетки, исходя из условий задачи.

Чтобы заполнить клетку F 0 в первой таблице, необходимо просуммировать произведения элементов столбца х 0 на элементы столбца с 0 , т.е.

F 0 = 600∙0 + 520∙0 +600∙0 =0.

Чтобы заполнить целевую строку в первой таблице, необходимо соответствующее значение с j вычесть из суммы произведений элементов столбца х j на элементы столбца с 0 .

Для столбца х 1 величина двойственной оценки будет определяться

(0∙80+0∙15+0∙5) – 15=-15;

Для х 2: (0 35+0 60+0 5) – 20=-20;

х 3: (0 10+0 0+0 90) – 5=-5 и т.д.

В итоге первая симплексная таблица будет выглядеть так:

Таблица 1

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

Определение

Решение считается оптимальным , если все значения чисел в целевой строке положительны.

Если полученное решение не является оптимальным, то его можно улучшить. Для этого нужно:

1. Выбрать максимальное по абсолютной величине отрицательное значение числа в целевой строке.

В нашем примере таким числом будет (-20), находящееся в столбце «х 2 ». Именно это значение задает ключевой столбец .

Обратите внимание:

Ключевой столбец показывает, какое из х j войдет в новое решение задачи. В нашем случае - неизвестное х 2 .

Обратите внимания:

Чтобы включить в новое решение неизвестное х j , улучшающее это решение, необходимо вывести из базисного решения одно из х j , входящее в него.

2. Выбрать минимальное значение частного от деления элементов столбца х 0 на элементы ключевого столбца. Результаты этих расчетов заносятся в столбец «» симплексной таблицы.

В нашем примере эти отношения равны:

Минимальное значение соответствует х 5 и равно 8,67. Это отношение задает ключевую строку .

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

В нашем примере ключевой элемент равен 60 и находится на пересечении столбца х 2 и строки х 5 .

Обратите внимание:

Ключевым не может быть столбец, все элементы которого оказались отрицательными или нулевыми.

Просуммировать элементы матрицы по строкам (начиная от столбца х 0 и кончая столбцом х 6). Полученные суммы записываются в столбец «».

Преобразовать ключевую строку . Для этого

Каждый элемент ключевой строки делится на ключевой элемент, начиная с элемента столбца «х 0 »;

Фрагмент

В столбце р 1 записывается х 2 вместо х 5 ;

В столбце с j записывается значение критерия оптимальности при х 2 , т.е. 20.

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

При пересчете величины функции цели получаем:

Аналогичным образом поступаем со всеми другими элементами таблицы. В итоге получаем новую симплексную таблицу.

Таблица 2.

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

Примечание 1.

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

Примечание 2.

Величина функции цели должна равняться сумме произведений элементов столбца с j на элементы столбца х 0 .

Самостоятельно дорешайте эту задачу. В результате должно получиться:

F=236.7; x 1 =3.31; x 2 =7.8; x 3 =6.05.

Примечание 3.

В столбце «» записываются частные от деления элемента в ключевом столбце и строке i на ключевой элемент.

Примечание 4.

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

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

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

Пусть x 1 , x 2 , x 3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

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

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1

Исходная таблица для задачи имеет следующий вид:

	x 1	x 2	...	x n-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1,1	a 1,2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2,1	a 2,2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

x 1 , x 2 , x n - исходные переменные, x n+1 , x n+2 , x n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные , а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным .

Алгоритм симплекс-метода.

Подготовительный этап

Приводим задачу ЛП к каноническому виду

F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1

a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2

.......................................

a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

	x 1	x 2	...	x n-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1,1	a 1,2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2,1	a 2,2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно .

Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.

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

Шаг 2. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b 0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b 0)

a 0,l =min{a 0,i }

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

b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0

k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.

Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

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

Правила преобразований симплексной таблицы.

При составлении новой симплекс-таблицы в ней происходят следующие изменения:

Вместо базисной переменной x k записываем x l ; вместо небазисной переменной x l записываем x k .
ведущий элемент заменяется на обратную величину a k,l "= 1/a k,l
все элементы ведущего столбца (кроме a k,l) умножаются на -1/a k,l
все элементы ведущей строки (кроме a k,l) умножаются на 1/a k,l
оставшиеся элементы симплекс-таблицы преобразуются по формуле a i,j "= a i,j - a i,l x a k,j / a k,l

Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.

Преобразуемый элемент a i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

ВВЕДЕНИЕ

Цель данного курсового проекта - составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить её симплекс - методом и составить программу для решения задачи этим методом на ЭВМ.

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА

1.1 Математическое программирование

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x 1 , x 2 , ... , x n) при ограничениях g i (x 1 , x 2 , ... , x n) * b i , где g i - функция, описывающая ограничения, * - один из следующих знаков £ , = , ³ , а b i - действительное число, i = 1, ... , m. f называется функцией цели (целевая функция).

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

Задачу линейного программирования можно сформулировать так. Найти max

при условии: a 11 x 1 + a 12 x 2 + . . . + a 1n x n £ b 1 ;

a 21 x 1 + a 22 x 2 + . . . + a 2n x n £ b 2 ;

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

a m1 x 1 + a m2 x 2 + . . . + a mn x n £ b m ;

x 1 ³ 0, x 2 ³ 0, . . . , x n ³ 0 .

Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.

В матричной форме задачу линейного программирования записывают следующим образом. Найти max c T x

при условии

где А - матрица ограничений размером (m´n), b (m ´ 1) - вектор-столбец свободных членов, x (n ´ 1) - вектор переменных, с Т = - вектор-строка коэффициентов целевой функции.

Решение х 0 называется оптимальным, если для него выполняется условие с Т х 0 ³ с Т х, для всех х Î R(x).

Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный (прямой, простой) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод

Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

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

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

Формируется симплекс-таблица.

Рассчитываются симплекс-разности.

Принимается решение об окончании либо продолжении счёта.

При необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

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

Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m , а в задачи минимизации - с положительными m . Таким образом из исходной получается новая m - задача.

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

1.4 Модифицированный симплекс - метод

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

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

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

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

Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов: оборудованием 1-го типа - а 1 , оборудованием 2-го типа - а 2 , оборудованием 3-го типа - а 3 .На производство единицы изделия В идёт времени, часов: оборудованием 1-го типа - b 1 , оборудованием 2-го типа - b 2 , оборудованием 3-го типа - b 3 .

На изготовление всех изделий администрацияпредприятия может предоставить оборудование 1-го типа не более, чем на t 1 ,оборудование 2-го типа не более, чем на t 2 , оборудование 3-го типа не более, чем на t 3 часов.

Прибыль от реализации единицы готового изделия А составляет a рублей, а изделия В - b рублей.

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

а 1 = 1 b 1 = 5 t 1 = 10 a = 2

а 2 = 3 b 2 = 2 t 2 = 12 b = 3

а 3 = 2 b 3 = 4 t 3 = 10

3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

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

Построение математической модели осуществляется в три этапа:

1. Определение переменных, для которых будет составляться математическая модель.

Так как требуется определить план производства изделий А и В, то переменными модели будут:

x 1 - объём производства изделия А, в единицах;

x 2 - объём производства изделия В, в единицах.

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

Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x 1 + 3x 2 (рублей). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения переменных x 1 и x 2 , максимизирующих целевую функцию F = 2x 1 + 3x 2 .

3. Формирование системы ограничений.

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

x 1 + 5x 2 £10;3x 1 + 2x 2 £ 12 ; 2x 1 + 4x 2 £ 10 .

Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности:

x 1 ³ 0 ; x 2 ³ 0 .

Таким образом, математическая модель задачи представлена в виде: определить план x 1 , x 2 , обеспечивающий максимальное значение функции:

max F = max (2x 1 + 3x 2)

при наличии ограничений:

x 1 + 5x 2 £10;

3x 1 + 2x 2 £ 12 ;

2x 1 + 4x 2 £ 10 .

x 1 ³ 0 ; x 2 ³ 0 .

3.2 Решение задачи вручную

Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.