Шпоры

1.1. Математические модели задач ЛП

Задача ЛП заключается в отыскании вектора , минимизирующего (максимизирующего) линейную целевую функцию, переменные которой подчинены линейным ограничениям

Точка (вектор) координаты которой удовлетворяют условиям (2) – (5), называется допустимым решением (точкой, вектором) задачи ЛП или планом.

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

Допустимое решение, на котором целевая функция (1) обращается в минимум (максимум), называется оптимальным решением (оптимальным планом).

1.2. Рекомендации к составлению математических моделей

Для использования стандартных вычислительных алгоритмов ЛП требуется математическая запись модели. Таким образом, необходимо умение переводить словесное описание задачи на язык математических символов.

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

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

Наконец, составляется целевая функция, которая в математической форме отражает критерий выбора лучшего варианта.

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

2.1. Каноническая форма задачи ЛП

Для численного решения задачи ЛП требуется предварительно привести ее к каноническому виду:

………………………

Каноническая форма (КФ) задачи характеризуется следующими тремя признаками:

1. однородная система ограничений в виде системы уравнений;

2. однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче;

3. минимизация (максимизация) целевой функции.

Известно, что для произвольной задачи ЛП можно построить эквивалентную ей каноническую задачу ЛП (эквивалентность двух задач означает, что оптимальному решению одной задачи соответствует оптимальное решение другой)[1,2,3].

2.3. Общие рекомендации к графическому решению задач ЛП

1. Графически могут решаться [1]:

1. задачи, заданные в произвольной форме, содержащие не более двух переменных;

2. задачи, заданные в канонической форме, с числом свободных переменных ;

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

2. Основной формой для графического решения является 1-й тип задач. Поэтому, если встречается 2-й или 3-й тип задач, то предварительно их модель должна быть приведена к первому типу.

3. Решение задач 1-го типа выполняется в два этапа:

этап 1 -- построение области допустимых решений;

этап 2 -- построение в допустимой области оптимального решения.

4. При построении области допустимых решений может встретиться один из трех случаев:

а) пустая область – задача не имеет решения из-за несовместности системы ограничений в области допустимых решений;

б) выпуклый многоугольник – задача всегда имеет оптимальное решение;

в) неограниченная выпуклая многогранная область – в зависимости от направления вектора c (вектора коэффициентов целевой функции L) задача может иметь или не иметь решение. Последнее связано с неограниченностью целевой функции в области допустимых решений.

5. Если оптимальное решение существует, то возможен один из трех исходов:

а) оптимальное решение единственное и совпадает с одной из вершин области;

б) оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины областии :

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

3.2. Алгоритм симплекс-метода для задачи на минимум

Шаг 0 Подготовительный этап. Приводим задачу ЛП к специальной форме

Шаг 1 Составляем симплекс-таблицу, соответствующую специальной форме:

	B		…		…
L			…		…
			…		…
..	..	…………
			…		…
..	..	…………
			…		…

Заметим, что этой таблице соответствует допустимое базисное решение задачи (15). Значение целевой функции на этом решении

Шаг 2 Проверка на оптимальность. Если среди элементов индексной строки симплекс – таблицы нет ни одного положительного элемента то, оптимальное решение задачи ЛП найдено: .Алгоритм завершает работу.

Шаг 3 Проверка на неразрешимость. Если среди есть положительный элемент , а в соответствующем столбце нет ни одного положительного элемента , то целевая функция L является неограниченной снизу на допустимом множестве. В этом случае оптимального решения не существует. Алгоритм завершает работу.

Шаг 4 Выбор ведущего столбца q. Среди элементов выбираем максимальный положительный элемент .Этот столбец объявляем ведущим (разрешающим).

Шаг 5 Выбор ведущей строки p. Среди положительных элементов столбца находим элемент , для которого выполняется равенство:Строку p объявляем ведущей (разрешающей). Элемент объявляем ведущим (разрешающим).

Шаг 6 Преобразование симплексной таблицы.

Составляем новую симплекс-таблицу, в которой:

а) вместо базисной переменной записываем , вместо небазисной переменной записываем ;

б) ведущий элемент заменяем на обратную величину

в) все элементы ведущего столбца (кроме ) умножаем на ;

г) все элементы ведущей строки (кроме ) умножаем на ;

д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».

Из элемента вычитается произведение трех сомножителей:

первый - соответствующий элемент ведущего столбца;

второй - соответствующий элемент ведущей строки;

третий - обратная величина ведущего элемента .

Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

Шаг 7 Переход к следующей итерации осуществляется возвратом к шагу 2.

3.3. Алгоритм симплекс-метода для задачи на максимум

Алгоритм симплекс-метода для задачи на максимум отличается от алгоритма для задачи на минимум только знаками индексной строки коэффициентов в целевой функции , а именно:

На шаге 2: :

На шаге 3 . Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4: .

5.2. Алгоритм метода Гомори

Шаг 1. Симплекс-методом находим оптимальное решение задачи (22) без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В случае алгоритм завершает работу.

Шаг 2. Пусть оптимальная таблица имеет вид:

	b		…
L			…
			…
…	…	…………..
/			…

Если элементы – целые, то оптимальное решение является целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.

Шаг 3. Среди дробных компонент таблицы выбираем элемент с максимальной дробной частью и по строке i составляем дополнительное ограничение:

Здесь - целая часть числа (наибольшее целое число, не превышающее число ).

Шаг 4. Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к шагу 2.

Замечания.

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

2. На шаге 4 двойственный симплекс-метод применяется до тех пор, пока не будет получена оптимальная симплексная таблица (возможно потребуется несколько итераций).

Если на шаге 4 в базис вводится переменная дополнительного ограничения , то эта строка вычеркивается из симплексной таблицы (соответствующее ограничение является избыточным)

6.2. Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

	1	…	n
1		…
…	…	…	…	…
m		…
		…		=

Базисными клетками транспортной таблицы являются клетки с отличными от нуля положительными перевозками, остальные клетки – свободные. Базисные клетки образуют опорный план транспортной задачи, ели выполняются два условия:

1. сумма перевозок в каждой строке равна запасу в данной строке;

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

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

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях [1,3].