Симплексный метод (183907)

Посмотреть архив целиком

Задача 1.

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

Вариант 3.

Найти наибольшее значение функции f(X) = - x1 - x2 + 2x3 при ограничениях

2x1 + x2 + x3  2

x1 - x2 + x3  1,

xj  0, j = 1, 2, 3.

Решение.

Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x4,5  0.

f(X) = - x1 - x2 + 2x3  max

2x1 + x2 + x3 + x4 = 2

x1 - x2 + x3 + x5 = 1,

xj  0, j = 1, 2, 3, 4, 5.

Каноническая задача имеет необходимое число единичных столбцов, т. е. обладает очевидным начальным опорным решением.

Очевидное начальное опорное решение (0; 0; 0; 2; 1).

Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах


Номер симплекс-таблицы

Базис


Cj


Ci

B

-1

-1

2

0

0

Q

A1

A2

A3

A4

A5

0

A4

0

2

2

1

1

1

0

2:1 = 1

A5

0

1

1

-1

1

0

1

1:1 = 1

j

-

0

1

1

-2

0

0

 

1

A4

0

1

1

2

0

1

-1

1:2 = 1/2

A3

2

1

1

-1

1

0

1

 

j

-

2

3

-1

0

0

2

 

2

A2

-1

1/2

1/2

1

0

1/2

-1/2

 

A3

2

3/2

3/2

0

1

1/2

1/2

 

j

-

5/2

7/2

0

0

1/2

3/2

 


Начальное опорное решение (0; 0; 0; 1; 1), соответствующее симплекс-таблице 0, неоптимальное, так как в  - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А5, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А5 выводим из базиса, а А3 - вводим в базис. После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 1; 1; 0) не оптимально, так как в  - строке есть отрицательные значения, в столбце А2.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А2 - вводим в базис. Опорное решение, соответствующее симплекс-таблице 2 (0; 1/2; 3/2; 0; 0) - оптимально, так как в  - строке нет отрицательных значений.

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

х1 = 0, х2 = 1/2 = 0,5; х3 = 3/2 = 1,5; fmax = -10 - 10,5 + 21,5 = 2,5.

Задача 2.

Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.

Задание 2. Решить полученную задачу линейного программирования графическим методом.

Задание 3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.

Вариант 3.

Из 505 м2 ткани нужно сшить не более 150 женских и не более 100 детских платьев. На пошив одного женского и детского платья требуется соответственно 3 м2 и 1 м2 ткани. При реализации каждого женского платья получают 10 ден. единиц прибыли, а детского – 5 ден. единиц. Сколько нужно сшить женских и детских платьев, чтобы получить наибольшую прибыль?

Решение.

Задание 1.

Обозначим x1 и x2 количество женских и детских платьев, соответственно (план пошива). Очевидно, x1,2  0 и целые. Так как женских платьев должно быть не более 150, то x1  150, аналогично, для детских платьев получаем x2  100. Расход ткани на план пошива (x1, x2) составит 3x1 + x2 м2, эта величина не должна превышать запаса ткани 505 м2. Следовательно, должно выполняться неравенство 3x1 + x2  505.

Прибыль от продажи платьев составит f(X) = 10x1 + 5x2 ден. единиц, и она должна быть наибольшей

Получаем экономико-математическую модель задачи:

Найти максимум функции f(X) при заданных ограничениях

f(X) = 10x1 + 5x2  max

3x1 + x2  505

x1  150

x2  100

x1,2  0, целые.

Задание 2.

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

Прямые ограничения x1,2  0 выделяют первую четверть плоскости.

Проведем прямую 3x1 + x2 = 505 через точки (110; 175) и (175; -5). Подставим в первое неравенство координаты точки (0; 0): 30 +10 = 0 < 505, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую x1 = 150 и выберем левую полуплоскость.

Проведем прямую x2 = 100 и выберем нижнюю полуплоскость.

Множество допустимых решений – это многоугольник ABCDO.

Построим линию уровня целевой функции f(X) = 10x1 + 5x2 10x1 + 5x2 = 0 через точки (0; 0 ) и (-10; 20). Вектор-градиент {10; 5} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение.

Из чертежа видно, что наибольшее значение целевой функции будет на линии уровня, проходящей через точку В.

Координаты этой точки найдем из системы

3x1 + x2 = 505,

x2 = 100.

x1 = 135,

x2 = 100.

fmах = 10 135 + 5 100 = 1850 ден. единиц.

Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане пошива следует сшить женских платьев 135 шт., детских – 100 шт. При этом прибыль составит 1850 ден. единиц и будет наибольшей.


















Задание 3.

Двойственная задача.

Найти минимум функции g(Y) при ограничениях:

g(Y) = 505y1 + 150y2 + 100y3  min

3y1 + y2  10

y1 + y3  5

y1,2,3  0.

Оптимальное решение прямой задачи Х = (135; 100). Подставим его в ограничения этой задачи

3135 + 1100 = 505

135 < 150

100 = 100.

Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения:



Так как для оптимального решения прямой задачи второе ограничение выполняется как неравенство, то в оптимальном решении двойственной задачи y2 = 0.

Так как для оптимального решения прямой задачи х1 > 0и х2 > 0, то оба ограничения двойственной задачи выполняются как равенство. Для нахождения решения двойственной задачи получаем систему

y2 = 0

3y1 + y2 = 10

y1 + y3 = 5.

Получаем решение: y1 = 10/3, y2 = 0, y3 = 5/3.

Найдем значение целевой функции двойственной задачи:

g(Y) = 50510/3 + 1500 + 1005/3 = 5550/3 = 1850.

Получили gmin = fmax = 1850 ден. единиц.

Так как значения прямой и двойственной функций равны, то Y = (10/3; 0; 5/3) является оптимальным решением двойственной задачи (по первой теореме двойственности).

Задача 3.

Задание 1. Записать исходные данные задачи в виде транспортной таблицы, определить, открытой или закрытой является транспортная задача.

Задание 2. Сформулировать экономико-математическую модель исходной транспортной задачи.

Задание 3. Найти оптимальный план перевозок, отметив при этом единственность или неединственность оптимального плана.

Вариант 3.

Картофель из четырех районов должен быть перевезен в три хранилища. Запасы картофеля в районах соответственно равны 400 т, 500 т, 800 т и 500 т. Возможности хранилищ соответственно равны 700 т, 800 т и 700 т. Затраты на перевозку одной тонны картофеля из первого района в каждое из хранилищ равны соответственно 1, 4 и 3 ден. единиц; аналогичные затраты на перевозку из второго района составляют 7, 1 и 5 ден. единиц, из третьего - 4, 8 и 3 ден. единиц, из четвертого - 6, 2 и 8 ден. единиц. Найти план перевозок картофеля из районов в хранилища, при котором транспортные расходы были бы минимальными.


Случайные файлы

Файл
12345.rtf
162963.rtf
179784.rtf
123761.rtf
47314.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.