Линейное программирование

Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
Краткое сожержание материала:

Размещено на

Размещено на

Линейное программирование

Вариант №6

Задание №1. Решение симплексным методом:

(1.1)

(1.2)

(1.3)

Задача (1.1)-(1.3) является общей задачей линейного программирования (ЛП), так как система (1.1) состоит из неравенств, вводя дополнительные неизвестные х₃>0, х₄>0 и прибавляя их к левым частям первого и второго неравенства и отнимая неизвестную х₅>0 от левой части третьего неравенства, домножим третье неравенство на -1, получим основную задачу ЛП вида:

(1.4)

(1.5)

(1.6)

Не выполняя дополнительных преобразований, определяем, что основная форма (1.4)-(1.6) одновременно является и канонической формой задачи ЛП.

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

Таблица №1

Базисы	x0	x1	x2	x3	x4	x5	Ключевое отношение
х3	4	5	-2	1	0	0	-2
х4	4	-1	2	0	1	0	2
х5	-4	-1	-1	0	0	1	4
f	0	-1	-2	0	0	0

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

Таблица №2

Базисы	x0	x1	x2	x3	x4	x5	Ключевое отношение
х3	8	4	0	1	1	0	2
х2	2	-1/2	1	0	1/2	0	4
х5	-2	-1 1/2	0	0	1/2	1	1 1/3
f	4	-2	0	0	1	0

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

Так продолжаем до тех пор, пока, все элементы индексной строки не отрицательны (положительные и нули).

Таблица №3

Базисы	x0	x1	x2	x3	x4	x5	Ключевое отношение
х3	2 2/3	0	0	1	2 1/3	2 2/3	1
х2	2 2/3	0	1	0	1/3	-1/3	-8
х1	1 1/3	1	0	0	-1/3	-2/3	-2
f	6 2/3	0	0	0	1/3	-1 1/3

В новой таблице (Таблица №3) рассчитываем и записываем ключевую строку, Остальные строки подсчитываются по правилу двух перпендикуляров. Мы видим, что х₅ войдет в базисы, заменив собой х₃. Получаем новую таблицу (Таблица №4):

Таблица №4

Базисы	x0	x1	x2	x3	x4	x5
х5	1	0	0	3/8	7/8	1
х2	3	0	1	1/8	5/8	0
х1	2	1	0	1/4	1/4	0
f	8	0	0	1/2	1 1/2	0

В Таблице №4 все элементы индексной строки не отрицательные (положительные и нули), значит задача решена. Так оно и есть, значит, план является оптимальным, а значение, стоящее в индексной строке столбца х₀ есть максимальное значение целевой функции. Вычисления прекращаем и получаем: , .

Так же было проведена проверка с помощью MS Excel, встроенной функции «Поиск решения». На Рисунке 1 - Заполнение требуемых параметров, мы видим заданную систему; изменяемые ячейки, которые являются базисами; целевую ячейку, которая отображает максимальное значение целевой функции; сохраняемые модели, которые необходимы для хранения временных данных.

линейное программирование функция



Рисунок 1 - Заполнение требуемых параметров

На Рисунке 1 изображено не все, так же имеются формулы, которые написаны для расчета целевой функции и сохраняемых моделей. Формула для расчета целевой ячейки: произведение сумм коэффициентов перед неизвестными в целевой функции на изменяемые ячейки соответственно. Для сохраняемых моделей...