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

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

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

Вариант №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

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

Таблица №2

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

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

Таблица №3

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

Таблица №4

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

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

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

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

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

Рисунок 2 - Выполняемая программа

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

Задание №1. Построить графическое решение:

(1.1)

                    (1.2)

                            (1.3)

Система линейных ограничений (1.1) - (1.3), представлена в виде прямых, определим точки для построения прямых на плоскости:

) ;

) ;

) ;

Постоим получившиеся прямые на плоскости. Каждая прямая делит декартову плоскость на две полуплоскости:

Рисунок 3 - График

Так как изначально нам были даны неравенства то, следовательно, решение неравенства является множество точек, а решение системы является область, включающая точки, удовлетворяющие всем неравенствам.

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

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

Теперь построим целевую функцию. Целевую функцию можно изобразить в виде сетки параллельных прямых, достаточно для построения приравнять целевую функцию к любому значению и построить прямую (; (4;0); (0;2)). Та точка, через которую пройдет целевая функция при перемещении вдоль вектора нормали окажется последней в многоугольнике будет ответом. Эта тоска с координатами (2;3). Получаем ответ: . Для получения оптимального плана подставим координаты в целевую функцию и получим: , оптимальный план: .

Задание №2. Решить транспортную задачу

Решить транспортную задачу. Заданы мощности поставщиков аi (i=1,2,3), емкости потребителей bj (j=1,2,3) и матрица стоимостей перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

Исходные данные:

Таблица №5 - Исходные данные

Решить задачу можно в том случае если задача закрыта, то есть должно выполнять равенство: 50+18+12=14+20+22, получается 8056; введем дополнительного потребителя

-56=24.

Таблица №6 - Ввод дополнительного потребителя

Составим исходный план перевозок Х₁ (Рисунок 4) методом «северо-западного угла», распределяя мощности поставщиков по порядку между потребителями, так чтобы каждая перевозка была максимально возможной.

План перевозок оформим в виде таблицы, разделенной на клетки. В центре каждой клетки плана поместим перевозки , а в правом верхнем углу - стоимость перевозки единицы продукции. В клетки, соответствующие нулевым перевозкам, нули не вписываем, оставляя их пустыми. В таком случае план Х₁ будет содержать не больше, чем m+n-1 положительных перевозок или занятых клеток, где m - число поставщиков, n - число потребителей. Остальные компоненты плана Х₁, соответствующие нулевым перевозкам, будем называть свободными клетками. Если число занятых клеток K = m + n -1, то план перевозок называется невырожденным, если K < m + n - 1, то вырожденным.

Подсчитаем суммарную стоимость перевозок по плану Х₁:

Проверим план Х₁ (Рисунок 4) на оптимальность. Найдем потенциалы  поставщиков и потенциалы  потребителей.

Рисунок 4 - План Х₁ (План )

По условию для занятых клеток:

Один из потенциалов всегда задается произвольно, зададим . Тогда из системы получим , , , , , , . Эти потенциалы полезно записать справа и снизу от плана .

По условию для свободных клеток:

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

; 4 > 0; -1 < 3; 4 = 4

; -4 < 2; 4 < 7; 5 < 6

Мы видим, что не выполняется одно неравенство

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

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

Выбираем , то есть в качестве  выбирается наименьшая из перевозок, из которых  вычитается. При включении в план  перевозки =12 суммарная стоимость перевозок изменится на , то есть уменьшится на 48 ед. и для нового плана составит:

Рисунок 6 - План Х₂ (План )

По условию для занятых клеток:

По условию для свободных клеток:

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

; -1 < 3; 4 = 4; -4 > 0

; 3 > 2; 8 > 7; 9 > 6

Мы видим, что не выполняются три неравенство причем

;

;

.

Следовательно, план  можно улучшить, введя в план перевозку , для которой разность  оказалась меньше разностей . С этой целью составим цикл, имеющий начало в свободной клетке (3, 3), а остальные вершины - в занятых клетках, последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину . Цикл и последовательность увеличения и уменьшения перевозок изображено на рисунке 6.

Выбираем , то есть в качестве  выбирается наименьшая из перевозок, из которых  вычитается. При включении в план  перевозки =4 суммарная стоимость перевозок изменится на , то есть уменьшится на 12 ед. и для нового плана составит:

Рисунок 7 - План Х₃ (План )

По условию для занятых клеток:

По условию для свободных клеток:

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

; 6 = 6; 2 < 3; 7 > 4

; -1 < 0; 3 > 2; 8 > 7

Мы видим, что не выполняются три неравенство причем

;

;

.

Следовательно, план  можно улучшить, введя в план перевозку , для которой разность  оказалась меньше разностей . С этой целью составим цикл, имеющий начало в свободной клетке (2, 2), а остальные вершины - в занятых клетках, последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину . Цикл и последовательность увеличения и уменьшения перевозок изображено на рисунке 7.

Выбираем , то есть в качестве  выбирается наименьшая из перевозок, из которых  вычитается. При включении в план  перевозки =8 суммарная стоимость перевозок изменится на , то есть уменьшится на 24 ед. и для нового плана составит:

Рисунок 8 - План Х₄

По условию для занятых клеток:

По условию для свободных клеток:

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

; 9 = 9; 3 = 3; -4 < 4

; 0 < 2; 5 < 7; -3 < 0

Из уравнений и неравенств следует, что они выполняются оба условия критерия оптимальности плана перевозок. Следовательно, план перевозок Х₄ является оптимальным планом закрытой задачи, а  представляет собой наименьшую стоимость перевозок. Отбросив последний столбец плана Х₄, получим оптимальный план Х^* исходной открытой задачи, для которой  есть наименьшая стоимость перевозок.

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