183814 (629937), страница 2

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

Текст из файла (страница 2)

f(x) = 618+715+832+85+840+710+147+1613=1107

Рассмотрим процесс нахождения потенциалов для данного распределения.

Положим, Ui=0 V2=U1+C12=7; V5=U1+C15=7=U3+14=U4+16 U3= -7, U4= -9; V3=U4+C43= -1; V4=U2+8=U1+8 U2=U1=0; V4=8.

Найдем оценки: d_ij=(U_i+c_ij)-V_j:

11 0 15 0 0

(dij) = 13 1 11 0 8

0 -4 4 -3 0

8 -6 0 -5 0

Данный план не является оптимальным, т.к. есть отрицательные оценки.

Построим контур перераспределения для клетки (4,2). Наименьшая поставка в вершине контура со знаком “-” равна 13, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком “-” на 13 и увеличив поставки в клетках со знаком “+” на 13. результаты поставлены в таблице 2.

Суммарные затраты:

f(x) = 618+72+1013+832+85+840+7-23+14-7=1127

Положим U1=0

V2 = U1+C12=7=U4+10 U4 = -3

V3 = U4+8=5; V4=U1+8=8=U2+8 U2=0

V5 = U1+7= 7 = U3+14 U3= -7

V1 = U3+6= -1

dij = (Ui+Cij)-Vj

9 0 9 0 0

(dij) = 11 1 5 0 8

0 -3 -2 -3 0

14 0 0 1 6

Наличие отрицательных оценок свидетельствует о том, что план не является оптимальным. Построим контур перераспределения для клетки (3,2). Наименьшая поставка в вершине контура со знаком “-” равна 2. Произведем перераспределение поставок. Результаты представим в таблице 3.

Суммарные затраты:

f(x) = 618+102+1013+832+85+840+725+147=1119

Положим, U1=0 V4=8, V5=7; V4=U2+8 U2=0

V5 = U3+14 U3= 7-14= -7; V1= -7+6= -1; V2= -7+10= +3

V2=U4+10 U4=3-10= -7; v3= -7+8=1

9 4 13 0 0

(dij) = 13 5 9 0 8

2 0 2 -3 0

10 0 0 -3 2

Наличие отрицательных оценок свидетельствует о том, что план не является оптимальным. Построим контур перераспределения для клетки (3,4).

Наименьшая поставка в клетке со знаком “-” равна 5. Произведем перераспределение поставок результаты представим в таблице 4.

Суммарные затраты:

f(x) = 730+840+618+102+125+1013+832=1104

U1=0 V5= 7; U2=0 V4=8=U3+12 U3=-4

V1= 6-4=2, V2=10-4=+6=U4+10; V3= -4+8= +4

8 1 10 0 0

(dij) = 10 2 6 0 8

0 0 2 0 3

10 0 0 0 5

Матрица оценок (dij) не содержат отрицательных величин данный план является оптимальным, т.к. С34 = 0, а клетка (3,4) не является запятой, то данный план не является единственным. Стоимость перевозок по этому плану, как было рассчитано ранее, равна f(x) = 1104.

3.6. Симплекс-метод решения задач линейного программирования.

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

Реализация алгоритма симплекс-метода.

1. Записать задачу в канонической форме: заменить все ограничения-неравенства с положительной правой;

2. Разделить переменные на базисные и свободные: перенести свободные переменные в правую часть ограничений-неравенств.

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

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

5. Выразить функцию цели через свободные переменные: базисные переменные, входящие в функцию, выразить через свободные переменные;

6. Вычислить полученное базисное решение и функцию цели на нем: приравнять к 0 свободные переменные;

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

8. Определить включаемую в базис и исключаемую из базиса переменные: если не все коэффициенты при свободных переменных в функции цели положительны (отрицательны), то следует выбрать свободную переменную, входящую в функцию цели с максимальным по модулю отрицательным (положительным) коэффициентом, и увеличивать ее до тех пор, пока какая-нибудь из базисных переменных не станет равной 0. Свободную переменную рассматриваем как новую базисную переменную (включаемую в базис), а базисную переменную рассматриваем как новую базисную переменную (исключаемую из базиса);

9. Используя новое разделение переменных на базисное и свободное, вернуться к пункту 3 и повторять все этапы до тех пор, пока не будет найдено оптимальное решение.

В заключение отметим, что определение оптимального решения распадается на два этапа:

• Нахождение какого-либо допустимого решения с положительным свободным членом;

• Определение оптимального решения, дающего экстрему целевой функции.

IV. Методы нелинейного программирования.

4.1. Основные понятия, постановка и методы решения задачи нелинейного программирования.

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

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

Z1(X1, X2,...,Xn) 0;

Z2(X1, X2,...,Xn) 0;

...................................

Zm(X1, X2,...,Xn) 0;

при Xi 0,

где Z1, Z2,…,Zm – соответствующие функции, характеризующие условие решения поставленной задачи (ограничения); Хi – искомые величины, содержащие решение задачи.

Целевая функция задается в виде:

y = f (X1, X2,…, Xn).

Причем по крайней мере одна из функций y, Z1, Z2,…, Zm – нелинейная.

Методами нелинейного программирования решаются задачи распределения неоднородных ресурсов.

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

Известны оценочные возможности (вероятности) начать бизнес в j-м регионе (Pj), а также эффективности использования i-го ресурса в n-м регионе (ij).

Распределение ресурсов по регионам характеризуется так называемым параметром управления (hij):

Характеристики

Список файлов курсовой работы