Нахождение опорного плана транспортной задачи

. ЛИНЕЙНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ, ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЕ ПОСТАНОВКА И СВОЙСТВА

1.1 Постановка задачи линейного программирования

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

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

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

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

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

Н

лист

Кп-км-п-44-2203-99

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

- выпуклое программирование - когда выпукла целевая функция, если рассматривается задача ее минимизации (либо выпуска, если ищется максимум), и выпукло множество, на котором решается экстремальная задача;

- квадратичное программирование - когда целевая функция квадратичная, а ограничения - линейные равенства и неравенства.

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

Важным разделом математического программирования является целочисленное программирование - когда на переменные накладываются условия целочисленности.

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

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

1. Задача решается относительно переменных .

В дальнейшем они будут записываться в виде либо вектора-столбца

( X1)

X = ( .. )

( Xn)

либо вектора-строки х = (х1, ..., хn).

Предполагается, что вектор х должен удовлетворять системе n линейных неравенств

a11x1+ …. +a1nxn <=>

am1x1+….+amnxn<=bm>

3. В экономических задачах присутствует дополнительное необходимое условие: координаты вектора х должны быть неотрицательными:

X >= 0 (2)

где 0 - нулевой вектор-столбец размерности n.

4. Целевая функция представляет собой линейную функцию переменных X1,…..,Xn

P1X1+…..PmXn=f(x1,….,xn) (3)

Лист

Кп-км-п-44-2203-99

5. Общая задача линейного программирования (ЛП) состоит в выборе вектора х, удовлетворяющего системе неравенств (1), (2) и максимизи­рующего целевую функцию ( 3 ). Математически задача ЛП записывается следующим образом:

P1X1+…..+PnXn max (x1<….xn)>

при условиях

{a11x1+…….+a1nxn<=b1}

{…………………………… } (5)

{am1x1+…….+amnxn<=bm}>

x1>=0, x2>=0,……,xn>=0 (6)

или

n

E pixi max

J=1 x1,..,xn

при условиях

n

{ E a1jxj<=bi

j=1

{…………

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать