Применение графического метода и симплекс-метода для решения задач линейного программирования

Содержание

Введение

Задание

1. Графический метод решения задачи линейного программирования

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

3. Решение задачи двойственной к исходной

4. Решение транспортной задачи

Выводы

Введение

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

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

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

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

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

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

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

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции задачи.

Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру.

Вектор C = (c₁, c₂) с координатами из коэффициентов целевой функции при x₁ и x₂ перпендикулярен к каждой из линий уровня. Направление вектора C совпадает с направлением возрастания целевой функции, что является важным моментом для решения задачи. Направление убывания целевой функции противоположно направлению вектора C.

Суть графического метода заключается в следующем. По направлению (против направления) вектора C в ОДР производится поиск оптимальной точки x* = (x₁*, x₂*). Оптимальной считается точка, через которую проходит линия уровня L_max (L_min), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Суть симплекс-метода состоит в следующем:

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

. Проверяют, не достигнут ли уже максимум целевой функции при найденном допустимом базисном решении.

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

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

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

симплекс графический программирование

Задание

1. Решить задачу линейного программирования графическим методом.

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

3. Имеются три пункта поставки однородного груза - А₁; А₂; А₃ и пять пунктов потребления этого груза - В₁; В₂; В₃; В₄; В₅. В пунктах А₁; А₂; А₃ находится 200; 450; 250 единиц груза соответственно, который надо доставить в пункты В₁; В₂; В₃; В₄; В₅ в количестве 100; 125; 325; 250; 100 соответственно. Расстояние между пунктами задано в километрах следующей матрицей:

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

1. Графический метод решения задачи линейного программирования

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат. Из условий ограничения получим область допустимых значений G

Рисунок 1. Графический метод решения задачи линейного программирования.

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

Решением этой системы уравнений будут координаты точки D: x1 = 6, x2 = 8. Подставляя эти значения в целевую функцию, получим окончательный ответ: .

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

Запишем задачу в канонической форме как того требует симплекс-метод, для этого введем две переменные y₄ и y₅, получим:

В получившейся системе отсутствуют базисные переменные, поэтому в первое и второе уравнения добавляем искусственные переменные y₆ и y₇. Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это y₆ и y_7. Получаем, так называемую, М-задачу:

 = (0, 0, 0, 0, 0, 2, 3)^T

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

В данную таблицу добавлена строка «φ». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (y₆ и y₇) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки «φ» определяется разрешающий столбец, пока она есть в таблице. Когда строка «φ» выйдет из таблицы (в базисе нет искусственных переменных), разрешающий столбец будет определяться по строке f. В данной таблице разрешающий столбец y₁, он выбран по наибольшей по модулю отрицательной оценке (-3). Разрешающая строка y₆ выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца. Это значит, что на следующей итерации симплекс-метода переменная y₁ из свободной перейдет в базисную, а переменная y₆ из базисной - в свободную. Запишем следующую симплекс-таблицу:

На следующей итерации строка «φ» выходит из таблицы, так как в базисе не остается искусственных переменных: