Задачи линейного программирования

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

Геометрическая интерпретация задачи ЛП

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

Пусть необходимо найти минимум целевой функции:

Переменные x₁ и x₂ должны быть неотрицательными.

Поэтому множество точек, являющихся возможными (допустимыми) решениями, может находиться в первом квадранте (см. рис. 4.6.1.). Неравенства–ограничения изображены в виде полуплоскостей, границами которых являются прямые (графики функций), полученные из неравенств путём отбрасывания знаков > ,< . Полуплоскости образуют выпуклый многоугольник (многоугольник решений – симплекс).

Линейная форма (линия уровня) для некоторого набора фиксированных значений переменной zпредставляет собой семейство параллельных прямых. Одна из них, которая пройдёт через вершину многоугольника «М», ближайшую к началу координат и даст минимум z(для координат вершины).

Графический способ решения (перемещение графика целевой функции по симплексу) приемлем только для двухмерных задач (задач на плоскости). Но геометрическое толкование задачи линейного программирования справедливо и для общего случая (m ограничений и n переменных). Каждое из соответствующих неравенству уравнений системы определяет некоторую гиперплоскость в n – мерном пространстве. Множество неотрицательных решений образует выпуклый многогранник в n – мерном пространстве. Линейная форма z-гиперплоскость, перемещая которую параллельно самой себе, будем получать множество точек пересечения её с выпуклым многогранником. Максимальное или минимальное значение линейной формы zдостигается в точках, являющихся вершинами выпуклого многогранника.

В силу трудности решения задачи графическим способом в случае m ограничений и n>2 переменных применяют другие методы решения задачи ЛП. Наиболее распространённым и удобным является симплекс методрешения задачи ЛП.

Для решения задачи линейного программирования симплекс-методом применяется специальный аппарат формальных преобразований математической модели. Рассмотрим некоторые его положения. Пусть задана основная задача линейного программирования (см. (4.6.1.) и (4.6.2)). Введя в левую часть каждого неравенства добавочную переменную, преобразуем его в уравнение и перейдём к другой, стандартной форме записи:

При этом значения b_i должны быть неотрицательными. В случае b_i <0 обе части уравнения умножают на» – 1». Заметим, что при максимизации zзадача сводится к стандартной путём замены: max z = – min (– z).

Систему (4.6.3) после несложных преобразований можно привести к виду:

Здесь b_i ³ 0. Коэффициенты при переменных < FONT> равны единице (+1). Данная система представлена в канонической форме записи. Если количество переменных превышает количество уравнений, то существует бесчисленное множество решений системы.

Пусть m < n. Разделим все переменные системы (4.6.4) на две части:

а) основные переменные, количество которых должно быть равно количеству линейно-независимых переменных (m);

б) неосновные переменные, количество которых будет равно n – m.

Назначим первые m переменных (x₁ , x₂ , …, x_m ) в качестве основных. Тогда систему (4.6.4) можно решить относительно x₁ , x₂ , …, x_m , если определитель m-го порядка, составленный из коэффициентов при переменныхx₁ , x₂ , …, x_m не равен нулю.

Придавая неосновным (независимым) переменным произвольные числовые значения, получим некоторое решение данной системы, причём каждому набору значений независимых переменных будет соответствовать одно определённое решение системы.

Основные (зависимые, несвободные) переменные будем называть базисными, неосновные (независимые, свободные) – небазисными переменными.

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

Допустимое базисное решение системы линейных уравнений при m <n – это такое решение, в котором неосновным (независимым, небазисным) переменным даны нулевые значения, а значения базисных переменных являются неотрицательными (решение на грани или вершине симплекса).

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

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

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

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

Симплекс-метод является наиболее распространенным универсальным методом. Существует несколько вариантов этого метода, рассмотрим один из них.

Необходимо предварительно выполнить следующие этапы:

– привести математическую модель к каноническому виду;

– определить начальное допустимое базисное решение задачи;

Пример:

L=3x₁ +2x₂ ®max

x₁ -x₂ £2,

2x₁ +x₂ £6,

x₁ , x₂ ³0

Приведем заданную модель к каноническому виду, введя свободные переменные x₃ и x₄ , превращающие неравенства в равенства. Переменные x₃ и x₄ входят в уравнение с коэффициентом единица и только один раз:

L=3x₁ +2x₂ ®max

x₁ -x₂ +x₃ =2,

2x₁ +x₂ +x₄ =6,

x_j ³0

где x₃ , x₄ - дополнительные переменные, x₁ , x₂ - свободные переменные, A_3, A₄ - начальный базис, A₀ -вектор ограничений.

Составим симплекс – таблицу, соответствующую каноническому виду:

Элементы строки D рассчитываем по формулам:

Для базисных переменных оценки всегда равны нулю.

Значение критерия для данного начального базиса будет равно нулю:

L=åc_i a_{i 0} =0*2+0*6=0;

Так как имеются D_j <0 приступаем к улучшению плана.

Первая итерация

В базис вводим вектор A₁ , которому соответствует минимальное значение D_j . Из базиса выводим вектор A₃ , так как минимальное q достигается при i=3.

Таким образом, элемент a₃₁ будет направляющим (в таблице выделен зеленым цветом).

Заполняем таблицу, соответствующую новому базисному решению.

Все элементы a_ij таблицы определяются по следущему рекуррентному соотношению:

где a_kr - направляющий элемент, l– номер итерации

Приведем расчет нескольких элементов таблицы:

Элемент a₄₂ =3 является направляющим (в таблице выделен зеленым цветом).

Так как в строке оценок полученного нового плана имеется отрицательное значение D_{j ,} приступаем ко второй итерации, продолжая улучшать план.

Вторая итерация

Элемент a₁₃ =1/3 является направляющим (в таблице выделен зеленым цветом).

Третья итерация

Поскольку все D_j ³0, то план представленный в данной таблице будет оптимальным.

Ответ:x₁ =0; x₂ =6; x₃ =8; x₄ =0; L=12;

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

Пример: Найти максимум функции

L=2x₁ +3x₂ -5x₃ ;

при ограничениях:

2x₁ +x₂ -x₃ ³7,

x₁ +2x₂ +x₃ ³6,

x₁ +4x₂ =8,

x_j ³0

Вводим в систему три искусственные переменные: x₆ , x_7, x₈ , позволяющие получить начальный базис.

Для исключения из базиса этих переменных последние вводятся в целевую функцию с большим отрицательным коэффициентом М (в задаче минимизации – с положительным М)

L¢=L-M*x₆ -M*x₇ -M*x₈ ®max

при ограничениях

2x₁ +x₂ -x₃ -x₄ +x₆ =7,

x₁ +2x₂ +x₃ -x₅ +x₇ =6,

x₁ +4x₂ +x₈ =8,

x_j ³0

Выбрав в качестве начального базиса векторы A_6, A₇ , A₈ , решаем полученную задачу с помощью табличного симплекс-метода.

Если в оптимальном решении такой задачи нет искусственных переменных, это и есть оптимальное решение исходной задачи.

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

Элемент a₈₂ =4 является направляющим (в таблице выделен зеленым цветом).

Столбцы, соответствующие искусственным переменным по мере вывода из базиса из расчета исключаются.

Элемент a₆₁ =7/4 является направляющим (в таблице выделен зеленым цветом).

Направляющий элемент a₇₃ =9/ 7 (в таблице выделен зеленым цветом).

Найдено оптимальное решение, так как все оценки неотрицательные и в базисе нет искусственных переменных:

x₁ =28/9, x₂ =11/9, x₃ =4/9, x₄ =0, L=23/3.

Список литературы

1. Разработка САПР. В 10 кн. Под ред. А.В. Петрова – М.: Высш. шк., 1990.

2. Системы автоматизированного проектирования: Учебн. пособие для ВУЗов: В 9 кн. / Под ред. И.П. Норенкова. – М.: Высш. шк., 1986. –159 с.

3. Основы построения систем автоматизированного проектирования / А.И. Петренко, О.И. Семенков. – 2-е изд., стер. – К.: Вища шк. Головное изд-во, 1985 – 294 с.

4. Справочник по САПР/ А.П. Будя, А.Е. Кононюк, К.П. Куценко и др.; Под ред. В.И. Скурихина. – К.: Техника, 1988. – 375 с.

5. Вермишев Ю.Х. Основы автоматизации проектирования. – М.: Радио и связь, 1988 – 288 с.

6. САПР изделий и технологических процессов в машиностроении / Р.А. Аллик, В.И. Бородянский, А.Г. Бурин и др. Под общ. ред. Р.А. Аллика. – Л.: Машиностроение, 1986. – 319 с.

7. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. 2-е изд., перераб. и доп. – М.: Финансы и статистика, 1989. – 351 с.

8. Грувер М., Зиммерс Э. САПР и автоматизация производства: Пер. с англ. – М.: Мир, 1987. – 528 с.

9. Гардан И., Люка М. Машинная графика и автоматизация конструирования: Пер. с франц. – М.: Мир, 1987. – 272 с., ил.

10.Корячко В.П. и др. Теоретические основы САПР: Учебник для ВУЗов. – М.: Энергоатомиздат, 1987. – 400 с., ил.

11.Робототехника и гибкие автоматизированные производства. В 9 кн. Учебное пособие для ВУЗов / Ю.М. Соломинцев и др. Под ред. И.М. Макарова. – М.: Высш. шк., 1986.

12.Хирн Д., Бейкер М. Микропроцессорная графика: Пер. с англ. – М.: Мир, 1987. – 352 с.

Поиск по сайту: