Навигация
Графическое решение задачи ЛП
20533
знака
10
таблиц
1
изображение
3.2. Графическое решение задачи ЛП
Построим область допустимых решений, в которой одновременно выполняются все ограничения. Искомое пространство решений – многоугольник ABCDEF. Пространство решений содержит бесконечное число точек, являющихся допустимыми решениями, но, несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает целевая функция модели z=3xE+2xI. На график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях 
, что позволяет определить наклон целевой функции и направление её увеличения. На видно, что оптимальному решению соответствует точка C, являющаяся пересечением прямых
Решив систему, получим
Тогда получаемый доход
тыс $.
Оптимальному решению всегда соответствует одна из допустимых угловых точек пространства решений. Какая из этих точек окажется оптимальной, зависит от наклона прямой, представляющей целевую функцию (т.е. от коэффициентов целевой функции).
4. Алгебраический метод решения задач
Использование графического метода удобно при решении задач ЛП с двумя переменными. При большем их числе необходимо применение алгебраичского аппарата.
Процесс решения задачи ЛП симплекс-методом носит итерационный характер: однотипные вычислительные процедуры в определённой последовательности выполняются до тех пор, пока не будет получено оптимальное решение.
4.1. Стандартная форма линейных оптимизационных моделей
1. Все ограничения записываются в виде равенств с неотрицательной правой частью. Исходное ограничение можно представить в виде равенства, прибавляя остаточную переменную к левой части ограничения (вычитая избыточную переменную из левой части).
Например,
Введём остаточную переменную s1>0, тогда
Правую часть равенства можно сделать неотрицательной, умножив обе части на –1.
2. Значения всех переменных модели неотрицательны.
Любую переменную yi, не имеющую ограничения в знаке, можно представить как разность двух неотрицательных переменных:
При любом допустимом решении только одна из этих переменных может принимать положительное значение, т.к. если 
, то 
, и наоборот. Это позволяет рассматривать 
как остаточную переменную, а 
– как избыточную.
3. Целевая функция подлежит максимизации или минимизации.
Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот.
Эквивалентность означает, что при одной и той же совокупности ограничений оптимальные значения переменных в обоих случаях будут одинаковы.
4.2. Симплекс-метод
Общую идею симплекс-метода проиллюстрируем на примере модели для задачи фирмы Reddy Mikks. На исходная точка алгоритма – начало координат (т. A) – начальное решение. От исходной точки осуществляется переход к некоторой смежной угловой точке (т. B или т. F). Её выбор зависит от коэффициентов целевой функции. Т.к. коэффициент при xE больше коэффициента при xI, а целевая функция подлежит максимизации, требуемое направление перехода соответствует увеличению xE (т. B). Далее указанный процесс повторяется для выяснения, существует ли другая экстремальная точка, соответствующая лучшему допустимому решению.
Правила выбора экстремальной точки:
1. Каждая последующая угловая точка должна быть смежной с предыдущей.
2. Обратный переход к предшествующей экстремальной точке не может производиться.
Чтобы описать рассмотренные процедуры формальными способами, необходимо определить пространство решений и угловые точки алгебраически. Требуемые соотношения устанавливаются по таблице:
| Геометрическое определение (графический метод) | Алгебраическое определение (симплекс-метод) |
| Пространство решений | Ограничения модели стандартной формы |
| Угловые точки | Базисные решения задачи в стандартном виде |
Похожие работы
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... среди математиков, его разделяли А.Н.Колмогоров, И.М.Гельфанд, В.И.Арнольд, С.П.Новиков и др. Нельзя не восхищаться естественностью и внутренней стройностью математической работ Л.В. по двойственности линейного программирования и их экономической интерпретацией. 2. О математической экономике как области математики и о некоторых ее связях А) Связи линейного программирования с функциональным и ...
... решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5). СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995. 2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного ...
... области (если допустимая область ограничена и не пуста); 3. ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи. Гл 2 Решение задач линейного программирования графическим способом на ЭВМ 2.1 Описание работы программы Программа написана с использованием собственных функций и процедур и трех стандартных модулей System, Crt и ...
0 комментариев