Оценочное отношение как найти

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

Решение:

I итерация:

1 этап: формирование исходной симплекс-таблицы.

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

В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3, х4, х5, х6, тогда свободными переменными будут х1,х2. Выразим базисные переменные через свободные:

Приведем целевую функцию к следующему виду:

На основе полученной задачи сформируем исходную симплекс-таблицу:

Таблица 5.3

Исходная симплекс-таблица

2 этап: определение базисного решения.

Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:

.

3 этап: проверка совместности системы ограничений ЗЛП.

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

4 этап: проверка ограниченности целевой функции.

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

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности.

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

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1» и колонка «х2». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2» содержит наименьший элемент (–3) в сравнении с колонкой «х1». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Таблица 5.4

Исходная симплекс-таблица

В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5», следовательно, она будет разрешающей.

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5» и колонки «х2».

9 этап: преобразование симплекс-таблицы.

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

9.1. Преобразование разрешающего элемента.

Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:

Полученный результат вписываем в аналогичную клетку таблицы 5.5.

9.2. Преобразование разрешающей строки.

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

9.3. Преобразование разрешающей колонки.

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

9.4. Преобразование остальных элементов симплекс-таблицы.

Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».

К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3» и колонки «», условно обозначим его «х3». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3»), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3» будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:

«х3»: .

Аналогично преобразуются значения других клеток:

«х3 х1»: ;

«х4»: ;

«х4 х1»: ;

«х6»: ;

«х6 х1»: ;

« »: ;

« х1»: .

В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).

II итерация:

1 этап: составление симплекс-таблицы.

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

Таблица 5.5

Симплекс-таблица II итерации

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):

.

Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности найденного базисного решения.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Таблица 5.6

Симплекс-таблица II итерации

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.

III итерация

1 этап: построение новой симплекс-таблицы.

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

Таблица 5.7

Симплекс-таблица III итерации

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):

.

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности найденного базисного решения.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Таблица 5.8

Симплекс-таблица III итерации

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.

IV итерация

1 этап: построение новой симплекс-таблицы.

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

Таблица 5.9

Симплекс-таблица IV итерации

2 этап: определение базисного решения.

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

.

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности найденного базисного решения.

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

7 этап: проверка альтернативности решения.

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

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

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

Решение:

I итерация:

1 этап: формирование исходной симплекс-таблицы.

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

В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3, х4, х5, х6, тогда свободными переменными будут х1,х2. Выразим базисные переменные через свободные:

Приведем целевую функцию к следующему виду:

На основе полученной задачи сформируем исходную симплекс-таблицу:

Таблица 5.10

Исходная симплекс-таблица

2 этап: определение базисного решения.

Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:

.

3 этап: проверка совместности системы ограничений ЗЛП.

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

4 этап: проверка ограниченности целевой функции.

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

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности найденного базисного решения.

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

7 этап: проверка альтернативности решения.

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

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

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

Решение:

I итерация

1 этап: составление исходной симплекс-таблицы.

Задача линейного программирования задана в каноническом виде. Составим расширенную матрицу и выделим с помощью метода Жордана-Гаусса базисные переменные. Примем в качестве базисных – переменные х1 и х2.

Умножим (поэлементно) первую строку на –3 и сложим со второй:

.

Умножим вторую строку на :

.

Сложим вторую с первой строкой:

.

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

Выразим базисные переменные через свободные:

Выразим целевую функцию также через свободные переменные, для этого подставим полученные значения базисных переменных в целевую функцию:

.

Запишем целевую функцию в следующем виде:

.

Составим исходную симплекс-таблицу:

Таблица 5.11

Исходная симплекс-таблица

2 этап: определение базисного решения.

Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:

.

Найденное базисное решение является вырожденным, т.к. имеется базисная переменная х2, равная нулю.

3 этап: проверка совместности системы ограничений ЗЛП.

Так как в таблице 5.11 имеется строка с отрицательным свободным числом (–1), в которой нет ни одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной), то согласно признаку несовместности (признак 1) система ограничений данной задачи не совместна (строка целевой функции при рассмотрении данного признака не учитывается). Следовательно, рассматриваемая задача линейного программирования не имеет решения.

Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности ее системы ограничений.

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

Симплекс-метод
основан на следующих свойствах ЗЛП:

1. Не существует
   локального экстремума, отличного от
   глобального. Другими словами: если
   экстремум есть, то он единственный.

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

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

4. Каждой угловой
   точке многогранника решений отвечает
   опорный план ЗЛП.

Существует две
разновидности симплексного метода:

• симплекс-метод с
  естественным базисом;

• симплекс-метод с
  искусственным базисом (М-метод);

• Симплекс-метод с
  естественным базисом.

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

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

I.
Если задача не приведена к каноническому
виду, то сделать это так, как в описано
в пункте №1. Получить расширенную систему
вида:

II. Исходную
расширенную систему заносим в первую
симплексную таблицу. Последняя строка
таблицы, в которой приведено уравнение
для линейной функции цели, называется
оценочной. В ней указываются коэффициенты
функции цели с противоположным знаком:
Δ_j =.
В левом столбце таблицы записываем
основные переменные (базис), в первой
строке таблицы — все переменные (отмечая
при этом основные), во втором столбце –
коэффициенты при основных переменных
системы с_i,
в третьем столбце – свободные члены
расширенной системы b₁,
b₂, …, b_m. Последний
столбец подготовлен для оценочных
отношений, необходимых при расчете
наибольшего возможного значения
переменной. В рабочую часть таблицы
(начиная с четвертого столбца и второй
строки) занесены коэффициенты a_ij
при переменных из расширенной системы.
Далее таблица преобразуется по
определенным правилам.

III. Проверяем
выполнение критерия оптимальности при
решении задачи на максимум — наличие
в последней строке отрицательных
коэффициентов Δ_j
< 0 (c_i > 0). Если таких
нет, то решение оптимально, достигнут
max F =

(в левом нижнем углу таблицы), основные
переменные принимают значения b_i
(третий столбец), неосновные переменные
равны 0, т.е. получаем оптимальное базисное
решение.

IV. Если критерий
оптимальности не выполнен, то наибольший
по модулю отрицательный коэффициент
Δ_j
< 0 в последней строке определяет
разрешающий столбец s.

Составляем оценочные
ограничения каждой строки по следующим
правилам:

1. , если b_i
   и a_is
   имеют разные знаки;

2. , если b_i
   = 0 и a_is
   < 0;

3. , если a_is
   = 0;

4. 0,
   если b_i
   = 0 и a_is
   > 0;

5. ,
   если
   
   a_i0
   и a_is
   имеют одинаковые знаки.

Определяем
.
Если конечного минимума нет, то задача
не имеет конечного оптимума (Fmax = ).
Если минимум конечен, то выбираем строку
q, на которой он достигается (любую,
если их несколько), и называем ее
разрешающей строкой. На пересечении
разрешающих строки и столбца находится
разрешающий элемент a_qs.

V. Переходим к
следующей таблице по правилам:

а) в левом столбце
записываем новый базис: вместо основной
переменной x_q – переменную
x_s,

б) в столбцах,
соответствующих основным переменным,
проставляем нули и единицы: 1 — против
“своей” основной переменной, 0 —
против “чужой” основной переменной,
0 — в последней строке для всех основных
переменных;

в) новую строку с
номером q получаем из старой делением
на разрешающий элемент a_qs;

г) все остальные
элементы a_qs
вычисляем по правилу прямоугольника:

Далее переходим
к п. III
алгоритма.

Пример
3.1. Решить задачу об использовании
ресурсов, приведенную в лекции,
с помощью симплексных таблиц.

Решение. Расширенная
система задачи имеет вид:

Линейную функцию
представим в виде F
– 2x₁
– 3x₂
= 0.

Заполняем первую
симплексную таблицу (табл.
3.1), в которой переменные x₃,
x₄, x₅,
x₆ основные.
Последняя строка заполняется коэффициентами
линейной функции с противоположным
знаком (см. п. II алгоритма).

Таблица 3.1

Базис	Коэф. при базисных переменных	Свободный член (План)	Переменные	Оценка
x1	x2	x3	x4	x5	x6
2	3	0	0	0	0
x3	0	18	1	3	1	0	0	0	18/3
x4	0	16	2	1	0	1	0	0	16
 x5	0	5	0	1	0	0	1	0	5
x6	0	21	3	0	0	0	0	1	
	F=0*18+0*16+0*5+0*21=0	Δj =	-2	-3	0	0	0	0

В соответствии с
п. III алгоритма проверяем
критерий оптимальности.

Δ_j
=
для всех j = 1, 2, …, 6:

Δ₁
=
0*1+0*2+0*0+0*3 – 2 = – 2

Δ₂
=
0*3+0*1+0*1+0*0 – 3 = – 3

Δ₃
=
0*1+0*0+0*0+0*0 – 0 = 0

Δ₄
=
0*0+0*1+0*0+0*0 – 0 = 0

Δ₅
=
0*0+0*0+0*1+0*0 – 0 = 0

Δ₆
=
0*0+0*0+0*0+0*1 – 0 = 0

В последней строке
имеются отрицательные коэффициенты.
Выбираем из них наибольший по модулю
(Δ₂ =
–3); второй столбец разрешающий,
переменная x₂
перейдет в основные (этот столбец отмечен
рамочкой). В соответствии с п.
IV находим оценочные отношения и
min{18/3; 16; 5;
} = 5.
Третья строка является разрешающей
(отмечена горизонтальной стрелкой и
рамочкой). На пересечении разрешающих
строки и столбца стоит разрешающий
элемент a₁₁ = 1.

Строим табл.
2 по правилам п. V
алгоритма:

а) в новом базисе
основные переменные: x₃,
x₄, x₂,
x₆;

б) расставляем
нули и единицы; например, в клетке,
соответствующей основной переменной
x₃ по столбцу и
строке, ставим 1, а в клетке,
соответствующей основной переменной
x₃ по строке, а
основной переменной x₂
— по столбцу, ставим
0 и т.п. В последней строке против
всех основных переменных ставим
0. Третья строка получается делением
на разрешающий элемент a₁₁
= 1. Остальные клетки
заполняем по правилу прямоугольника.
Например:
,

и т.д.

Получим вторую
симплексную таблицу (табл.
3.2)

Таблица
3.2

Базис	Коэф. при базисных переменных	Свободный член	Переменные	Оценка
x1	x2	x3	x4	x5	x6
2	3	0	0	0	0
 x3	0	3	1	0	1	0	-3	0	3
x4	0	11	2	0	0	1	-1	0	11/2
→ x2	3	5	0	1	0	0	1	0	
x6	0	21	3	0	0	0	0	1	7
	F=0*3+0*11+3*5+0*21=15	Δj =	-2	0	0	0	3	0

Δ_j
=
для всех j = 1, 2, …, 6:

Δ₁
=
0*1+0*2+3*0+0*3 – 2 = – 2

Δ₂
=
0*0+0*0+3*1+0*0 – 3 = 0

Δ₃
=
0*1+0*0+3*0+0*0 – 0 = 0

Δ₄
=
0*0+0*1+3*0+0*0 – 0 = 0

Δ₅
=
0*(-3)+0*(-1)+3*1+0*0 – 0 = 3

Δ₆
=
0*0+0*0+3*0+0*1 – 0 = 0

Критерий оптимальности
вновь не выполнен (Δ₁
<0). Теперь первый
столбец разрешающий; x₁
— переходит в основные, min{3/l;
11/2; ;
7}= 3; первая строка разрешающая, a₁₁
— разрешающий элемент.

Новая симплексная
таблица примет вид табл. 3.3.

Таблица 3.3

Базис	Коэф. при базисных переменных	Свободный член	Переменные	Оценка
x1	x2	x3	x4	x5	x6
2	3	0	0	0	0
→ x1	2	3	1	0	1	0	-3	0	
 x4	0	5	0	0	-2	1	5	0	5/5
x2	3	5	0	1	0	0	1	0	5/1
x6	0	12	0	0	-3	0	9	1	12/9
	F=2*3+0*5+3*5+0*12=21	Δj =	0	0	2	0	-3	0

Δ_j
=
для всех j = 1, 2, …, 6:

Δ₁
=
2*1+0*0+3*0+0*0 – 2 = 0

Δ₂
=
2*0+0*0+3*1+0*0 – 3 = 0

Δ₃
=
2*1+0*(-2)+3*0+0*(-3) – 0 = 0

Δ₄
=
2*0+0*1+3*0+0*0 – 0 = 0

Δ₅
=
2*(-3)+0*5+3*1+0*9 – 0 =-6 + 3=-3

Δ₆
=
2*0+0*0+3*0+0*1 – 0 = 0

И на этот раз
критерий оптимальности не выполнен (Δ₅
<0); пятый столбец
и вторая строка разрешающие,
a₂₅
= 5 — разрешающий элемент.

Переходим к табл.
3.4

Таблица
3.4

Базис	Коэф. при базисных переменных	Свободный член	Переменные	Оценка
x1	x2	x3	x4	x5	x6
2	3	0	0	0	0
x1	2	6	1	0	-1/5	3/5	0	0
x5	0	1	0	0	-2/5	1/5	1	0
x2	3	4	0	1	2/5	-1/5	0	0
x6	0	3	0	0	3/5	-9/5	0	1
	F=2*6+0*11+3*4+0*3=24	Δj =	0	0	4/5	3/5	0	0

Δ_j
=
для всех j = 1, 2, …, 6:

Δ₁
=
2*1+0*0+3*0+0*0 – 2 = 0

Δ₂
=
2*0+0*0+3*1+0*0 – 3 = 0

Δ₃
=
2*(-1/5)+0*(-2/5)+3*2/5+0*3/5 – 0 = 4/5

Δ₄
=
2*(3/5)+0*1/5+3*(-/5)+0*(-9/5) – 0 = 3/5

Δ₅
=
2*0+0*1+3*0+0*0 – 0 = 0

Δ₆
=
2*0+0*0+3*0+0*1 – 0 = 0

Критерий оптимальности
выполнен (все Δ_j
> 0), значит F_max
⁼ 24, оптимальное
базисное решение (6; 4; 0; 0; 1;
3).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Тема. Симплекс-метод решения задач линейного программирования.
^

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

1) определения какого-либо первоначального допустимого базисного решения задачи;

2) правила перехода к лучшему решению;

3) проверки оптимальности допустимого решения.

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

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

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

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены.

1. Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и неосновные (свободные). В качестве основных переменных на первом шаге следует выбрать (если это возможно) такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений. При этом нет таких уравнений системы, в которые не входит ни одна из этих переменных.

базисные неизвестные –

свободные неизвестные –

1. По расширенной системе строим симплекс-таблицу

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
		…			…
				…		1	…	0
…	…	…	…	…	…	…	…	…
				…		0	…	1
F	0			…		0	0	0

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

^

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

• Все элементы разрешающей строки делим на разрешающий элемент. Полученную строку обозначаем *.
• Вычисление элементов остальных строк, включая F-строку.

Новая строка = текущая строка её коэффициент в разрешающем столбце строку *

1. См. п 4.

Вопросы.

1. Какую роль играет в симплексном методе разрешающий (ведущий) элемент?
2. При каких условиях допустимое базисное решение является оптимальным?
3. В чем состоит симплексный метод решения задач ЛП?
4. Каким образом следует выбирать разрешающий столбец при переходе от одного к другому базису?
5. Каким образом следует выбирать разрешающую строку?
6. Какие последствия влечет отрицательность коэффициентов разрешающего столбца?
7. Можно ли симплексным методом решить задачу линейного программирования, если на некоторые ее переменные не наложены условия неотрицательности?

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

1. 

Решение:

Расширенная система задачи имеет вид:

Базисные неизвестные —

Свободные неизвестные —

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

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

Находим оценочные отношения. Третья строка является разрешающей. На пересечении разрешающих строки и столбца стоит разрешающий элемент (1).

Таблица №1

	Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
№1		18	1	3	1	0	0	0
№2		16	2	1	0	1	0	0	16
№3		5	0	1	0	0	1	0	5
№4		21	3	0	0	0	0	1	–
№5	F	0	-2	-3	0	0	0	0

Строим таблицу №2

Новые базисные неизвестные —

Свободные неизвестные —

Коэффициенты таблицы №2 вычисляем следующим образом:

Новая строка №3 = строка №3/1 — обозначим результат *

Новая строка №1 = строка №1 – 3×строка *,

Новая строка №2 = строка №2 – 1×строка *,

Новая строка №4 = строка №4 – 0×строка *,

Новая строка №5 = строка №5 – (-3)×строка *,

Новая симплекс-таблица, соответствующая новому базису, имеет следующий вид.

Таблица №2

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
	3	1	0	1	0	-3	0	3
	11	2	0	0	1	-1	0
	5	0	1	0	0	1	0	–
	21	3	0	0	0	0	1	7
F	15	-2	0	0	0	3	0

Критерий оптимальности в таблице №2 снова не выполнен.

Таблица №3.

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
	3	1	0	1	0	-3	0	–
	5	0	0	-2	1	5	0
	5	0	1	0	0	1	0	5
	12	0	0	-3	0	9	1
F	21	0	0	2	0	-3	0

Таблица №4.

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
	6	1	0			0	0
	1	0	0			1	0
	4	0	1			0	0
	3	0	0			0	1
F	24	0	0			0	0

Критерий оптимальности таблицы №4 выполнен, значит

1. 

1. 

1. 

1. 

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

Вид ресурса	Вид товара	Объём ресурса
1	2	3	4
Сырьё (кг)	3	5	2	4	60
Рабочая сила (ч)	22	14	18	30	400
Оборудование (станко-часы)	10	14	8	16	130
Прибыль на ед. товара (ден. ед.)	30	24	56	48	max

По этим исходным данным решить следующие задачи:

а) выяснить, какой ассортимент товара надо выпускать, чтобы прибыль была максимальной;

б) определить оптимальный ассортимент при дополнительном условии: первого товара выпустить не более 7 ед., второго — не менее 8 ед., а третьего и четвертого — в отношении 1:2.

1. Для изготовления изделий № 1 и № 2 имеется 180 кг металла. На изготовление одного изделия № 1 расходуется 2 кг металла, а изделия № 2 – 3 кг. Составить план производства, обеспечивающий получение наибольшей выручки от продажи изделий, если отпускная цена одного изделия № 1 равна 13 руб., а изделия № 2 — 17 руб., причем изделий № 1 требуется изготовить не более 60, а изделий № 2 — не более 40.

1. Для изготовления трех видов продукции П₁, П₂, П₃ используются три вида сырья S₁, S₂, S₃, запасы которых указаны в таблице. Известны количества единиц сырья S₁, S₂, S₃, необходимые для производства единиц продукции П₁, П₂, П₃ соответственно, и стоимость реализации каждой единицы готовой продукции.

Вид сырья	Запасы (ед. объёма)	Вид продукции
П1	П2	П3
S1	2106	3	3	9
S2	2340	10	9	15
S3	650	5	5	1
Стоимость продукции (ден. ед.)	80	60	50

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

Понятие и алгоритм

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

Метод был разработан в 1947 году математиком из США Бернардом Данцигом. Предложенный способ оказался весьма эффективным для решения задач, связанных с оптимизацией использования ограниченных ресурсов. То есть он позволяет оценить и откорректировать параметры системы, а также получить качественные аналитические результаты.

Существует два подхода решения задачи:

• графический;
• симплексный.

Первый можно использовать для оптимизационного решения двухмерных задач. Например, существует два производственных цикла по сборке ящиков. Выпуск товара характеризуется ограничением в поставках древесины и временем формовки изделия. Для одного необходимо 30 досок, а для другого — 40. Поставщики доставляют в неделю 2 тыс. единиц материала. Первый ящик собирается за 15 минут, а второй — за 30. Нужно определить, какое количество ящиков необходимо производить за неделю на первом конвейере и на втором. При этом первое изделие приносит 10 рублей прибыли, а второе — пять. Время изготовление ограничено 160 часами.

Решение заключается в принятии за Х1 и Х2 количество выпущенных ящиков. Затем — в нахождении максимальной еженедельной прибыли и описании процесса ограничения в виде уравнения.

Это типовая двухмерная задача, условия неотрицательности которой определяются границами прямых: 30*Х1 + 4 0*Х 2 ≤ 2000 (для досок) и 20*Х 1 ≤ 50*Х 2 = 1600 (для сборки). Отложив по оси ординат Х1, а Х2 по абсцисс, и указав на них точки соответствующие уравнениям, можно будет подобрать оптимальное решение для использования сырья и времени.

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

Симплекс-метод при базисном решении

Впервые способ был изложен Данцигом в книге «Линейное программирование, его обобщения и применения», изданной на русском языке в 1966 году. Эта теория основывалась на вычислительной процедуре и представлялась в виде стандартных алгебраических форм. Основное направление метода заключается в указании способа нахождения опорного решения, переходе к другому, более оптимальному расчёту и определении критериев, позволяющих остановить перебор опорных вариантов.

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

1. Свести поставленную задачу к канонической форме путём переноса свободных членов в правую часть и ввода дополнительных переменных. В случае отрицательных переменных неравенство умножается на -1. Если в записи используется знак «меньше или равно», переменная используется положительная, в противном случае — отрицательная.
2. В зависимости от количества вводимых значений все переменные принимаются за основные. Их необходимо выразить через неосновные и перейти к базовому решению.
3. Через неосновные переменные выражается функция цели.
4. Если при решении отыскивается ответ с максимумом или минимумом линейной формы и все неосновные переменные получаются только положительными, то задача считается выполненной.
5. Если найденный максимум (минимум) линейной формы в функции имеет одну или несколько неосновных переменных с отрицательными коэффициентами, необходимо перейти к новому базисному решению.
6. Из переменных, входящих в форму с отрицательными или положительными коэффициентами, выбирается наибольшая (по модулю) и переводится в основные.

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

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

Двухфазный способ

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

Например, существует ограниченность, описываемая функцией:

F = C 1 X 1+ C 2 X 2+…+ CnXn. Используется условие, что Х1Р1+Х2Р2+…+Х(m +1) P (m +1)+ +… XnPn = Р0, где Х j больше либо равно 0 (j =1, n). Принимается, что среди чисел bi (i =1, m) имеются отрицательные.

Решением будет выражение: х= (b1; b2;…; bm ;0;…;0), однако этот ответ не будет разрешать задание, так как к нему могут относиться и отрицательные числа. Так как векторы Р1, Р2… Рм единичные, то каждый из них можно описать линейной областью, состоящей из них же. При этом коэффициентами разложения векторов Рj по области будут числа: Xij = aij (i =1, m; j =1, n) по модулю.

Выражение х= ( b1; b2;…; bm ;0;…;0) определяется базисом. Называют его псевдоплан. Считается, что если дельта j больше либо равна нулю, то для любого: j ( j =1, n ) по модулю. В то же время если в псевдоплане с находимым базисом существует хотя бы одно отрицательное число, то тогда задача вообще не будет иметь планов. Но когда для этих отрицательных чисел верно, что аij меньше нуля, то можно будет перейти к новому псевдоплану.

Объяснение псевдоплана помогает построить алгоритм двойственного метода. Если взять за основу х = (b1; b2;…; bm ;0;…;0) и представить это выражение псевдопланом, то, учитывая исходные данные, можно составить симплекс-таблицу. В ней часть элементов будет отрицательная. Так как дельта j должна быть больше либо равна нулю, то при отсутствии таких чисел в таблице уже будет записан оптимальный план. В обратном случае выбирается по модулю наибольшее из чисел с минусом.

Принцип решения задачи включает следующее:

• нахождение псевдоплана;
• проверка его на оптимальность;
• выбор разрешающей строки путём нахождения абсолютной величины отрицательного числа, отношения элементов (m+1) и соответствующей им строке;
• нахождение нового псевдоплана.

Если анализ оптимален, считается, что найдено верное решение. В другом случае устанавливается неразрешимость задачи либо составляется новый псевдоплан. Делается это в результате пересчёта табличных данных, например, методом Жордана-Гаусса.

Пример задачи

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

Задачи линейного программирования (ЗЛП) позволяют выбрать оптимальную загрузку при перемещении какого-либо товара из одних мест в другие. Во вводных данных указывается число пунктов отправления (м) и количество мест назначения (n). Первые обозначаются как А1, А2…Ам, а вторые – В1, В2…Вn. За аi принимается объём продукции на складе, а bi – потребность. Затраты на перевозку с i пункта в j обозначаются Сij.

Главная задача — составить план таким образом, чтобы общая стоимость была минимальна. Пусть дано четыре песчаных карьера, с которых необходимо поставить песок на четыре склада. При этом осуществляться перевозки должны за определённую стоимость. Составляем таблицу.

Записываем уравнение ограничения. Сумма всего перевезённого песка с первого карьера должна быть меньше или равна 140. Поэтому можно записать: x11+x12+x12+x14+T1 = 140, где Т1 переменная для хранения остатка. Сумма ограничений будет записана как х11+х21+х31 =115. Аналогичные уравнения составляют и для оставшихся карьеров.

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

• A0 – последний столбец из матрицы;
• Сб – стоимость перевозок;
• Х11, Т3 – данные из полученной матрица.

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

Наибольшее число определяется пересечением ранее выбранных значений, на базе которых создают новый базис. После в соответствии с единичными базисами меняют Сб и Хб. Операцию повторяют до тех пор, пока не исчезнут все положительные числа из последней строки. Заполняют новую таблицу.

Расчёт в Excel

Для включения пакета анализа в программе необходимо перейти в раздел «Параметры» и выбрать строчку «Перейти». В новом окне найти строчку «Пакет анализа», кликнуть по ней и нажать кнопку ОК.

Затем понадобится загрузить и открыть шаблон для проверки в Excel. Используя манипулятор типа «мышь» или клавиатуру, выбрать ячейку G4 и выполнить команду «Сервис/Поиск решения». Далее указать исходные данные, а после нажать кнопку «Выполнить».

Полученное решение можно представить в форме отчёта, содержащего:

1. Результаты – содержит информацию об исходных и конечных значениях целевой и влияющих ячеек, дополнительные сведения об ограничениях.
2. Устойчивость — отчёт, включающий данные о чувствительности решения к малым изменениям.
3. Пределы – включают исходные и конечные значения, а также верхние и нижние границы значений, которые принимают влияющие ячейки при введённых ограничениях.

Онлайн-сервис для чайников

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

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

1. «Семестр» (semestr.ru).
2. «Мир математики» (matworld.ru).
3. «Высшая математика» (math-pr.com).
4. «Матзона» (mathzone.ru).
5. «Контрольная работа» (kontrolnaya-rabota.ru).

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