Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Стандартная форма задачи ЛП

В теории Л П задачи приводят к стандартной форме, в которой целевая функция минимизируется, а все ограничения заданы в виде равенств с неотрицательными переменными. Зная решение задачи ЛП в стандартной форме, можно найти решение задачи Л П в других формах записи. Для приведения задачи к стандартной форме используют следующие правила [2, 3]:

1) максимизация целевой функции равносильна минимизации целевой функции;

2) ограничения в виде неравенств

приводятся к стандартной форме путем введения дополнительной избыточной (балансной) неотрицательной переменной х,»+1 Для этого в неравенстве (7.37) ограничение переносится из правой части в левую. Обозначим левую часть неравенства новой переменной:

Неравенство х'п { > 0 будет выполнено, если

Избыточная переменная определяет превышение значения левой части неравенства над границей;

3) ограничения в виде неравенств

приводятся к стандартной форме путем введения дополнительной остаточной (фиктивной) неотрицательной переменной для чего в неравенстве (7.38) ограничение переносится из правой части в левую, правая и левая части умножаются на — 1, что приведет к изменению знака неравенства; обозначим левую часть неравенства новой переменной:

Неравенство *'„+. ^ О будет выполнено, если

Остаточная переменная показывает остаток (неиспользованное количество) сырья или другого имеющегося в количестве Ьх ресурса.

В общем случае для т неравенств при преобразовании их в равенства необходимо добавить т дополнительных переменных. Вместо исходной матрицы А размерностью т х п задача ЛП в стандартной форме будет иметь матрицу [А ±1] размерностью тх(п + т),

т.е. первые п столбцов новой матрицы равны исходной матрице А, а последние т столбцов представляют собой единичную т х т матрицу I.

В матричном виде задачу ЛП, приведенную к стандартной форме, можно записать так

где — вектор дополнительных переменных, или вектор

невязки;

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

где

Вместо хк в ограничения записываются новые переменные х' к и х" к, и переменных становится п + 1. Вектор коэффициентов в целевой функции расширяется за счет добавления т нулевых компонент.

Второй способ преобразования задачи ЛП с произвольной переменной в стандартную форму заключается в устранении этой переменной совместно с одним из уравнений. Например, рассмотрим уравнение, у которого коэффициент при xY не равен нулю:

Тогда переменная хj может быть представлена линейной комбинацией других переменных и константой Ьк Подстановка полученного выражения во все другие уравнения вместо х{ дает новые условия задачи с переменными х2, х3,..., хп. Более того, использованное /-е уравнение будет равно нулю и, следовательно, может быть исключено из рассмотрения. В результате этих операций получим условия задачи Л П в стандартной форме с п — 1 переменными и aw —1 ограничениями. После решения задачи значение переменной хх может быть найдено из уравнения (7.39).

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

В матричных обозначениях задача ЛП в канонической (стандартной) форме может быть представлена в следующем виде: Минимизировать (максимизировать) функцию

при условиях х > 0; Ах = Ь.

Матрица А действительная, имеет размерность тхп и ранг т.

Рассмотренный выше двумерный пример с пошивом костюмов приведем к следующему виду:

с ограничениями

В матричной форме записи векторы имеют вид:

расширенная матрица.

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

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

В нашем примере имеются 4 переменных для двух уравнений. Поэтому две любые переменные можно выбрать в качестве базисных, а две другие приравнять нулю. Число вариантов определяется по формуле числа сочетаний п/(п — т)т — 4!/(4 — 2)!2! = 6:

Найдем решение уравнений (7.40) для всех вариантов и запишем их в табл. 7.3.

Таблица 7.3. Решения системы уравнений (7.40)

Вариант

*1

х2

*3

х4

*5

1

0

0

1700

1600

0

2

0

425

0

-525

н/д

3

0

320

420

0

А

4

566,6

0

0

466,6

С

5

800

0

-700

0

н/д

6

300

200

0

0

В

Из 6 возможных вариантов решений два являются недопустимыми (н/д), так как значения переменных отрицательны. Оставшиеся 4 варианта соответствуют 4 вершинам ОДР, показанной на рис. 7.14.

Базисные решения двумерной задачи ЛП

Рис. 7.14. Базисные решения двумерной задачи ЛП

В теории ЛП доказаны следующие утверждения.

Утверждение 1. Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Утверждение 2. ОДР является выпуклым множеством. Непустое множество решений основной задачи ЛП образует выпуклый многогранник.

Утверждение 3. Базисные допустимые решения соответствуют вершинам выпуклого множества, т.е. все крайние точки ОДР задачи ЛП полностью определяются базисными решениями системы Ах = Ь.

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

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

Решение задачи методом перебора вершин является трудоемким, так как при большом п количество углов (вершин) будет очень большим. Для сокращения числа операций используют симплекс-метод, предложенный Г. Данцигом в 1947 г.

КОНТРОЛЬНЫЕ ВОПРОСЫ

  • 1. Какие задачи сервиса могут быть решены с использованием метода линейного программирования (ЛП)?
  • 2. Как записывается задача Л П?
  • 3. Какой план называется опорным?
  • 4. Что такое область допустимых решений, какой вид она может иметь и какими свойствами должна обладать?
  • 5. Каков порядок графического решения двумерной задачи Л П?
  • 6. Какой критерий оптимизации используется в задачах сервиса? Чем он отличается от критерия оптимизации в экономических задачах?
  • 7. Что такое зависимые и независимые потребности?
  • 8. Что такое стандартная форма задачи ЛП? Как к ней преобразовать задачу ЛП?
  • 9. Что такое базисное решение задачи ЛП? Какие из базисных решений будут допустимы?
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>