Методы решения задач линейной оптимизации

Задача линейной оптимизации заключается в определении оптимального значения линейной целевой ф-ции при линейньк ограничениях. Существует несколько методов решения задач линейной оптимизации.

1) Графический метод - основан на геометрической интерпретации задачи и может быть использован для решения задач с 2 переменными.

Рассмотрим задачу линейного программирования, состоящую в нахождении max и min значения функции.

F=c1x1+c2x2

A11x1+A12x2 >(<) b1

Am1x1+Am2x2> (<)bm

Для того, чтобы решить задачу линейно графическим методом нужно:

1) Построить прямые, ур-ния которых задаются из ограничений заменой знаков неравенства на знаки равенств.

2) Определить полуплоскость, задаваемую каждым ограничением.

3) Найти многоугольник решений, образующийся в результате пересечения всех полуплоскостей

4) Построить вектор С с координатами {с1, с2}

5) Построить линию уровня c1x1+c2x2=h, h=const

6) Перемещать линии уровня в направлении вектора С для получения точки, в которой функция принимает наибольшее значение, и в обратном направлении- для нахождения минимума.

7) Определение координат точки max, min и вычисление значения целевой функции в ней.

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

Каноническая форма характеризуется условиями:

1) Целевая функция стремится к минимуму (если она стремится к максимуму то умножается на -1)

2) Правые части всех ограничений должны быть неотрицательны.

3) Все ограничения записываются в виде равенств. Преобразование неравенств в равенства осуществляется путем введения дополнительной неотрицательной переменной, если знак неравенства <, то дополнительная переменная добавляется к левой части, если знак >, то отнимается. Вектор Х=(х1..хn) называется допустимым решением или планом. План х*, при котором целевая функция принимает оптимальное значение называется оптимальным. Переменные, каждые из которых входят только в одно уравнение ограничений с коэффициентом 1 называются базисными, остальные свободные.

Приравнивание базисной переменной правой части ограничений, а свободные переменные к 0, дает одно из частных решений ЗЛП. Симплекс метод основан на последовательном переходе от одного опорного плана к другому с целью минимизации целевой функции.

Основные шаги алгоритма:

1) Приведение задачи к канонической форме;

2) Составление симплекс таблицы;

3) Вычисление оценок. Если все оценки меньше 0, то решение найдено. Если есть хоть одна оценка больше 0 задача не имеет решения.

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

5) Определение ведущей строки по правилу: bs/ask =min bi/aik, ask-ведущий элемент. Номер ведущей строки показывает в каком уравнении будет оставлена базисная переменная.

6) Пересчет элементов симплекс таблицы, при этом элементы ведущей строки bs, as1..asn, делятся на ведущий элемент, остальные переменные пересчитываются по правилу прямоугольника.

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

В результате формируется задача, называемая расширенной по отношению к исходной. В процессе решения задач оптимизации искусственные переменные стремятся к 0. Оценки состоят из 2 частей, одна из которых зависит от М, а другая не зависит.. Исходные данные расширенной задачи заносятся в симплекс таблицу. В процессе решения искусственные переменные выводятся из базиса.

Таким образом метод искусственного базиса включает следующие этапы:1) Составление расширенной задачи

2)Определение опорного плана расширенной задачи

3) Вывод искусственной переменной из базиса с использованием Симплекс метода

4) Определение оптимального плана обычным симплекс методом.