Решение задач линейного программирования

Совместные задачи ЛП (множество 0 непустое) всегда имеют решение, хотя не обязательно единственное. Решение х* достигается на вершине многогранника О допустимых планов. На этом факте основаны все методы решения задач ЛП. Рассматриваются только узловые точки, лежащие на границе множества О. Они

определяются, как решения уравнений, отвечающих неравенствам. При малой размерности задачи п= 1/2/3 можно пользоваться графическим способом решения, обеспечивающим хорошую наглядность. Широко распространенным является симплекс – метод.

Для применения симплекс- метода задача ЛП приводится к стандартному виду.

• все ограничения преобразуются к виду равенств с неотрицательными правыми частями (за счет введения дополнительных переменных в неравенства);

• все переменные рассматриваются как неотрицательные (за счет замены знаков коэффициентов);

• задача решается на максимум целевой функции.

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

1. Выбирается начальное допустимое решение, Обычно начало координат, х₀(0,..,.0).

2. Рассматриваются соседние (смежные, лежащие на той же грани, что и выбранная) вершины.

3. Переходим к новой вершине, если в ней значение целевой функции больше.

4. Возврат в прежнюю вершину не возможен.

Алгоритмы симплекс- метода реализованы во многих пакетах прикладных программ. В частности в Пакете Экономических Решений (ПЭР), являющемся русифицированной версией пакета QSВ. В данном пакете приведение модели к стандартному производится автоматически.

Применение линейного программирования для экономических задач.

Термин «программирование» применяется в данном случае потому, что задачи ЛП естественно возникают при разработке планов (программ) экономической деятельности, которая всегда происходит при ограничениях. связанных, в частности, с недостатком ресурсов (неравенства ) или директивными заданиями (неравенства ). Разработка объемных планов производства, выбор оптимальных маршрутов транспортных перевозок, распределение заданий по видам оборудования, достижение оптимальной загрузки оборудования можно проводить с помощью линейного программирования. Поэтому для переменных х используют термин «план»; «допустимый план» — план, удовлетворяющий ограничениям х  О, «оптимальный план» х* — план, на котором целевая функция F(х) достигает своего максимума или минимума А*=F(х*). Наглядным примером является следующая модель.