Размещено на http://www.allbest.ru/

1. Геометрическое истолкование задачи линейного программирования

В декартовой системе координат находим решение системы неравенств.

Для этого строим прямые.

x1-x2=1 по точкам (0; 1) (1; 0)

3x1-x2=6 по точкам (0; - 6) (2; 0)

ABC многоугольник решений

Вектор (6; -2) вектор целевой функции.

Проведём через любую точку прямую P', перпендикулярно вектору .

Перемещаем прямую Р' параллельно самой себе по направлению вектора , пока она не займёт относительно области ABC крайнего верхнего положения.

Это произойдёт, когда она пройдёт через точки B (2,5; 1,5) и С (2:0).

Оптимальное решение определяется координатами этих точек

Zmax=6*2-2*0=12

Zmax=6*2,5-2*1,5=12

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

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

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

Построение математической модели

x1 - количество изделия 1

x2 - количество изделия 2

x3 - количество изделия 3

x4 - количество изделия 4

Ограничения по ресурсам

4x1+5x2+10x3+2x4?30

5x1+15x2+20x3+5x4?70

40x1+10x2+15x3+20x4?150

Функция цели

Введем дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

4x1+5x2+10x3+2x4+x5=30

5x1+15x2+20x3+5x4+x6=70

40x1+10x2+15x3+20x4+x7=150

эти дополнительные переменные по экономическому смыслу

означают неиспользуемое сырьё при данном плане производства

Преобразованную систему уравнений запишем в векторной форме:

x1*P1+x2*P2+x3*P3+x4*P4+x5*P5+x6*P6+ x6*P7=P0, где

Симплекс - таблица

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

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

Определяем наименьшее, среди отношений Bi/Pi4

Вектор, который необходимо исключить P7. Разрешающий элемент - 20. Преобразуем исходную симплекс-таблицу относительно разрешающего элемента.

Определяем вектор подлежащий, который нужно ввести в базис, очевидно - это P2 (ему соответствует нулевое значение).

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

Определяем наименьшее, среди отношений Bi/Pi2.

Вектор, который необходимо исключить P6. Разрешающий элемент - 12,5.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента

Все ДZi>0, поэтому, полученное базисное решение

X1=0; X2=2,6; X3=0; X4=6,2; X5=4,6; X6=0; X7=0 является оптимальным, значение целевой функции для него равняется 112,5 усл. ед.

3. Построение двойственной задачи

Исходная задача (L):

Ограничения по ресурсам

4x1+5x2+10x3+2x4?30

5x1+15x2+20x3+5x4?70

40x1+10x2+15x3+20x4?150

Функция цели

Двойственная ей задача (L*), будет иметь вид: найти

при ограничениях

При этом оптимальное решение (X1; X2; X3; X4) задачи (L) и оптимальное решение (u1; u2; u3)

Задачи (L*) связаны соотношениями:

Которые называются отношениями двойственности, в линейном программировании, или соотношениями «дополняющей нежесткости».

Решение задачи (L) известно x1= 0 x2=2.6 x3= 0 x4=6.2 Z(мах)=112.5

Найдём решение задачи (L*) не прибегая к симплекс-методу, используя соотношение двойственности.

Так как x2=2.6>0 то для оптимальных решений задачи (L*) второе ограничение должно выполняться как равенство: 5u1+15u2+10u3=7,5

Так как x4=6,2>0 то для оптимальных решений задачи (L*) четвертое ограничение должно выполняться как равенство: 2u1+5u2+20u3=15

Подставляем оптимальное решение x2=2,6 x4=6,2 в первое неравенство задачи (L), видим, что 4*0+5*2,6+10*0+2*6,2=25,4<30 т.е. оно выполняется строго. Значит для оптимальных решений задачи (L*) значит u1=0.

Подставляем оптимальное решение x2=2,6 x4=6,2 во второе неравенство задачи (L), видим, что 5*0+15*2,6+20*0+5*6,2=70 т.е. сказать что u2=0 нельзя

Подставляем оптимальное решение x2=2,6 x4=6,2 в третье неравенство задачи (L), видим, что 40*0+10*2,6+15*0+20*6,2=150 т.е. сказать что u3=0 нельзя

Таким образом, оптимальное решение двойственной задачи (L*) удовлетворяет системе уравнений

Решая систему получаем

Оптимальное значение задачи (L*) равно

Zmin=30*0+70*0+150*0,75=112,5

Т.е выполнено второе условие, связывающее оптимальные решения задач (L) и (L*).

4. Транспортная задача

Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны b₁, b₂, b₃ и b₄ ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны a₁, a₂, a₃ ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

линейный симплексный двойственный задача

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

Первоначальный план найдём методом минимальной стоимости затрат на перевозку

Алгоритм нахождения базисного плана перевозок методом Фогеля.

1. по каждой строке и каждому столбцу определяют разность между двумя наименьшими тарифами и записывают её в дополнительные к исходной таблице строки и столбцы.

2. из полученных разностей выбирают наибольшую и отмечают её (жирный шрифт).

3. в стоке или столбце, где имеется наибольшая разность, выбирается клетка с наименьшим тарифом C_IJ и загружается наибольшей возможной перевозкой X_ij=min(a_i, b_j)

4. производится перерасчёт запасов и заявок на груз, клетки соответствующие тарифам, по которым уже невозможно что-либо перевезти, прочёркиваются, что соответствует нулевым значениям матрицы перевозок.

5. пункты 1-4 выполняются до тех пор, пока вся таблица не будет заполнена элементами матрицы перевозок

Стоимость плана S=5*90+11*10+1*90+5*60+2*20+4*80=1310 единицы

Определим, является ли этот план оптимальным

Метод потенциалов

Сосчитаем потенциалы по формуле

Формуле vj - ui=Cij i=1,2,3 j=1,2,3,4

В расчёте участвуют только занятые клетки

Предполагаем u1=0 и постепенно вычисляем остальные числа

Клетка А1В1: v1 - u1=C11 v1 -0 =5 v1 =5

Клетка А1В2: v1 - u2=C12 v2 -0 =11 v2=11

Клетка А3В2: v2 - u3=C32 11 - u3=5 u3 =6

Клетка А3В4: v4 - u3=C34 v4 -6 =4 v4=10

Клетка А3В3: v3 - u3=C33 v3 -6 =2 v3 =8

Клетка А2В3: v3 - u2=C23 8-u2 =1 u2=7

После того как все потенциалы найдены для каждой из свободных клеток определяем числа: ij=vj - ui - Cij

Клетка А1В3: 13=v3 - u1 - C13 13=8-9-0 = -1

Клетка А1В4: 14=v4 - u1 - C14 14=10-7-0 =3

Клетка А2В1: 21=v1 - u2 - C21 21=5-6-7= -8

Клетка А2В2: 22=v2 - u2-C22 22=11-3-7 =1

Клетка А2В4: 24=v2 - u2 - C24 24=10-8-7 = -5

Клетка А3В1: 31=v1 - u3 - C31 31=5-3-6 = -4

Числа 14 (клетка А1В4) и 22 (клетка А2В2) положительные - значит план не оптимальный и требует улучшения, следует переместить грузы в пределах клеток, связанных с данной свободной клеткой

Получили новый опорный план

Стоимость плана S=5*90+7*10+3*10+1*80+5*60+2*30+4*80=1270 единицы

Снова вычисляем потенциалы.

После того как все потенциалы найдены для каждой из свободных клеток определяем числа: ij=vj - ui - Cij

Клетка А1В2: 12=v2 - u1 - C12 12=10-11-0 = -1

Клетка А1В3: 13=v3 - u1 - C13 13=8-9-0 =-1

Клетка А2В1: 21=v1 - u2 - C21 21=5-6-7= -8

Клетка А2В4: 24=v4 - u2-C24 24=10-8-7 = -5

Клетка А2В4: 24=v2 - u2 - C24 24=10-8-7 = -5

Клетка А3В1: 31=v1 - u3 - C31 31=5-3-6 = -4

Среди чисел ij нет положительных чисел.

Значит план оптимальный.

Стоимость плана S=5*90+7*10+3*10+1*80+5*60+2*30+4*80=1270 единицы.

Размещено на Allbest.ru