Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули.

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

РЭ. НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

(0)-(2 * (-2+2M)):1	(-1-M)-(-2 * (-2+2M)):1	(-2+2M)-(1 * (-2+2M)):1	(-M)-(-1 * (-2+2M)):1	(-M)-(0 * (-2+2M)):1	(0)-(0 * (-2+2M)):1	(0)-(1 * (-2+2M)):1	(0)-(0 * (-2+2M)):1

Получаем новую симплекс-таблицу

Итерация №1.

• 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
• 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
• 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

min (-, 1: 3, -) = 1/3

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки

Формируем следующую часть симплексной таблицы.

Вместо переменной x7 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x1 плана 2 записываем нули.

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

Представим расчет каждого элемента в виде таблицы

(0)-(1 * (-5+3M)):3	(-5+3M)-(3 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(-2+M)-(1 * (-5+3M)):3	(-M)-(-1 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(2-2M)-(-1 * (-5+3M)):3	(0)-(1 * (-5+3M)):3

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

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

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

Q =

5

x 1

+

7

x 2

+

2

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

2

x 1

+

4

x 2

+

x 3

=

64

(1)

x 1

+

2

x 2

+

x 4

=

70

(2)

-

x 2

+

x 5

=

18

(3)

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

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

БП	x 1	x 2	x 3	x 4	x 5	Решение	Отношение
x 3	2	4	1	0	0	64	64 / 4 = 16
x 4	1	2	0	1	0	70	70 / 2 = 35
x 5	0	-1	0	0	1	18	--
Q	5	7	0	0	0	-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).

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

ВВЕДЕНИЕ

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

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 Решение задачи вручную

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

1. Приведение задачи к форме:

x 1 + 5x 2 £10;

3x 1 + 2x 2 £ 12 ;

2x 1 + 4x 2 £ 10 .

x 1 ³ 0 ; x 2 ³ 0 .

2. Канонизируем систему ограничений:

x 1 + 5x 2 + x 3 =10;

3x 1 + 2x 2 + x 4 = 12 ;

2x 1 + 4x 2 + x 5 = 10 .

x 1 ³ 0 ; x 2 ³ 0 .

A 1 A 2 A 3 A 4 A 5 A 0

3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам:

- текущее значение целевой функции - расчёт симплекс-разностей, где j = 1..6 .

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

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

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

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

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

Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.

Задача.

Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В - одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В - не более 40 шт. Причем, прибыль от реализации одного изделия А - 5 руб., а от В - 3 руб.

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

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

(3.10)

F = -5x 1 - 3x 2 → min.

Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.

I этап. Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов - столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные - верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения.

Таблица 3.4

базисные			свободные

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

Данной таблице 3.4 соответствует следующий опорный план:

(х 1 , х 2 , х 3 , х 4 , х 5) = (0, 0, 50, 40, 80).

Свободные переменные х 1 , х 2 равны 0; х 1 = 0, х 2 = 0. А базисные переменные х 3 , х 4 , х 5 принимают значения х 3 = 50, х 4 = 40, х 5 = 80 - из столбца свободных членов. Значение целевой функции:

-F = - 5х 1 - 3х 2 = -5 · 0 - 3 · 0 = 0.

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

Возможны различные ситуации.

1. В индексной F -строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу.

2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F →∞ неограниченно убывает.

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

III этап . Улучшение опорного плана.

Из отрицательных элементов индексной F -строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим "".

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

В нашем примере, , элемент 2 - разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).

Таблица 3.5

Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

1. В новой таблице таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В нашем примере: х 1 входит в базис, вместо х 5 , которая выходит из базиса и теперь свободная (табл. 3.6).

Таблица 3.6

базисные			свободные

2. На месте разрешающего элемента 2 записываем обратное ему число .

3. Элементы разрешающей строки делим на разрешающий элемент.

4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.

5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50.

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

Итак, . Записываем 10 на место, где было 50. Аналогично:

, , , .

Таблица 3.7

Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x 3 ,x 4 ,x 1 }. Значение целевой функции стало равно -200, т. е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.

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

Таблица 3.8

базисные			свободные
	х 3 = 30, х 2 = 40, х 1 = 20. Свободные переменные равны 0, х 5 = 0, х 4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: -F = -220 F = 220, в нашем примере функция исследовалась на min, и первоначально F max, поэтому фактически знак поменялся дважды. Итак, х * = (20, 40, 30, 0, 0), F * = 220. Ответ к задаче: Необходимо в план выпуска включить 20 изделий типа А , 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб. В конце этого параграфа приведем блок-схему алгоритма симплекс-метода, которая в точности повторяет этапы, но, возможно, для некоторых читателей будет более удобна в пользовании, т. к. стрелочки указывают четкую направленность действий. Ссылки над прямоугольниками в блок-схеме показывают, к какому этапу или подпункту относится соответствующая группа преобразований. правило нахождения первоначального опорного плана будет сформулировано в пункте 3.7. Вопросы для самоконтроля 1. Как строится симплекс-таблица? 2. Как отражается смена базиса в таблице? 3. Сформулируйте критерий остановки симплекс-метода. 4. Как организовать пересчет таблицы? 5. С какой строки удобно начинать пересчет таблицы?

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

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

В первой строке указываются все без исключения (и основные, и дополнительные) показатели критерия оптимальности, т.е. все коэффициенты, с которыми неизвестные входят в целевую функцию. В первый же столбец входит только часть коэффициентов при неизвестных в целевой функции, т.к. число строк в матрице равно числу дополнительных неизвестных. Эта часть состоит из показателей, номера которых указаны во втором столбце (р 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). Полученные суммы записываются в столбец «».

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

1. Каждый элемент ключевой строки делится на ключевой элемент, начиная с элемента столбца «х 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 . В этом случае основание матрицы пересчитывать не обязательно.