Применение графического метода и симплекс-метода для решения задач линейного программирования
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
и.
. Если оптимальное решение не найдено, то ищут новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение целевой функции.
Проверку того, достигнут ли при найденном допустимом решении максимум целевой функции, можно сделать путем поиска нового базисного решения. Для перехода к новому базисному решению одну из свободных переменных следует сделать базисной, при этом она будет отличаться от нуля, т.е. возрастет. Следовательно, если какая-либо из свободных переменных входит в выражение для целевой функции со знаком плюс и при ее увеличении целевая функция увеличивается, то максимум целевой функции не достигнут, и данную переменную следует превратить в базисную, сделав ее отличной от нуля. Однако при возрастании свободной переменной некоторые из базисных переменных будут уменьшаться. Поскольку отрицательные значения переменных недопустимы, то в качестве новой свободной переменной следует принять ту из базисных переменных, которая раньше других обращается в нуль.
Транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и пустых клеток.
симплекс графический программирование
Задание
1. Решить задачу линейного программирования графическим методом.
2. Решить задачу линейного программирования симплекс-методом, сформулировать и решить двойственную к исходной задаче.
3. Имеются три пункта поставки однородного груза - А1; А2; А3 и пять пунктов потребления этого груза - В1; В2; В3; В4; В5. В пунктах А1; А2; А3 находится 200; 450; 250 единиц груза соответственно, который надо доставить в пункты В1; В2; В3; В4; В5 в количестве 100; 125; 325; 250; 100 соответственно. Расстояние между пунктами задано в километрах следующей матрицей:
Требуется найти оптимальный план закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей. Рассмотреть два метода получения начального плана.
1. Графический метод решения задачи линейного программирования
Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат. Из условий ограничения получим область допустимых значений G
Рисунок 1. Графический метод решения задачи линейного программирования.
Направление возрастания целевой функции указано на рисунке 1. Соответственно, точкой максимума является точка D. Найдем ее координаты исходя из того, что она является точкой пересечения графиков (1) и (2). Для этого решим систему уравнений:
Решением этой системы уравнений будут координаты точки D: x1 = 6, x2 = 8. Подставляя эти значения в целевую функцию, получим окончательный ответ: .
. Решение задачи линейного программирования симплекс-методом
Запишем задачу в канонической форме как того требует симплекс-метод, для этого введем две переменные y4 и y5, получим:
В получившейся системе отсутствуют базисные переменные, поэтому в первое и второе уравнения добавляем искусственные переменные y6 и y7. Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это y6 и y7. Получаем, так называемую, М-задачу:
= (0, 0, 0, 0, 0, 2, 3)T
Данная система является системой с базисом, следовательно, для решения можно применить симплекс-метод. Запишем начальную симплекс-таблицу:
БПy1y2y3y4y5y6y7РешениеОтношениеf15200000-y62-11-101022/2 = 1y71210-10133/1 = 3?-3-1-211-1-1--
В данную таблицу добавлена строка ?. Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (y6 и y7) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки ? определяется разрешающий столбец, пока она есть в таблице. Когда строка ? выйдет из таблицы (в базисе нет искусственных переменных), разрешающий столбец будет определяться по строке f. В данной таблице разрешающий столбец y1, он выбран по наибольшей по модулю отрицательной оценке (-3). Разрешающая строка y6 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца. Это значит, что на следующей итерации симплекс-метода переменная y1 из свободной перейдет в базисную, а переменная y6 из базисной - в свободную. Запишем следующую симплекс-таблицу:
<