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

Математическое программирование (Вы можете использовать мат.программирование) помогает определить лучшее решение из предложенных. Решение задач математического программирования сводятся к решении задачи линейного программирования. Задачи математического программирования математические загадки, ответом на которые является оптимальное использование ресурсов для получения максимальной прибыли. Далее Вы узнаете, как решить задачу линейного программирования симплексным методом.

Каковы же способы решения задач линейного программирования? На этот вопрос Вы узнаете ответ, если продолжите читать. Существует три способа решения задач линейного программирования: простой и направленный переборы, симплекс метод. Каноническая форма задачи линейного программирования представлена на рисунке 1. Необходимо решить задачу линейного программирования симплексным методом.

madgicbox.com - математическое программирование методы решения задач

Рисунок 1 Каноническая форма задачи линейного программирования

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

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

Математическая модель задачи оптимизации включает целевую функцию, ограничения и граничные условия.

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

F = П1х1 + П2х2 + П3х3 + П4х4 → max

Прибыль на изделия составит в общем:

П = Ц – С

Отсюда, соответственно, дол:

П1 = 30 – 20 = 10

П2 = 45 – 25 = 20

П3 = 80 – 40 = 40

П4 = 85 – 55 = 30

Ограничения определяют зависимость между величинами требуемых и имеющихся ресурсов и могут быть записаны так:

1 + 3х2 + 8х3 + 4х4 ≤ 90

1 + 2х2 + 1х3 + 3х4 ≤ 80

Требуемые ресурсы указаны в левых частях, имеющиеся в правых.

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

xj  ≥  0   (j = 1,2,3,4)

Итак, математическая модель задачи представляется следующим образом:

F = 10х1 + 20х2 + 40х3 + 30х4 → max

1 + 3х2 + 8х3 + 4х4 ≤ 90

1 + 2х2 + 1х3 + 3х4 ≤ 80

xj  ≥  0   (j = 1,2,3,4)

Для приведения к канонической (стандартной) форме в левую часть каждого из неравенств введем дополнительную переменную. Получим:

F = 10х1 + 20х2 + 40х3 + 30х4 + 0(x5 + x6)

1 + 3х2 + 8х3 + 4х4 + x5 = 90

1 + 2х2 + 1х3 + 3х4 + х6 = 80

xj  ≥  0   (j =1,7)

  1. Определение начального опорного решения (плана).

Перепишем систему уравнений-ограничения виде:

x5 = 90 — 1х1 + 3х2 + 8х3 + 4х4

х6 = 80 — 2х1 + 2х2 + 1х3 + 3х4

В полученной системе переменные, находящиеся в правой части (х1, х2, х3, х4), называются свободными и приравниваются к нулю. Тогда переменные, стоящие слева (в данном случае дополнительные переменные х5, х6,), называются базисными и принимают значения, равные свободному члену (запасу ресурсов).      

Таким образом, начальное опорное решение: х1 = х2 = х3 = х4 = 0,   

х5 = 90, х6 = 80, или Х0 = (0, 0, 0, 0, 90, 80,).

При этом целевая функция F0, очевидно, равна нулю. Полученное решение поместим в симплексную таб. 1 Математическое программирование – задачи линейного программирования

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

madgicbox.com - основы математического программирования т1

  1. Проверка полученного решения на оптимальность.

Вычислим величину оценок для рассматриваемого задачи и результат запишем в таб. 2 Задачи линейного программирования:

1 = z1 – c1  =  (0 ∙ 1 + 0 ∙ 2)  – 10 = — 10 ;

2 = z2 – c2  =  (0 ∙ 2 + 0 ∙ 2)  – 20 = — 20 ;

3 = z3 – c3  =  (0 ∙ 8 + 0 ∙ 1)  – 40 = — 40 ;

4 = z4 – c4  =  (0 ∙ 4 + 0 ∙ 3)  – 30 = — 30 ;

5 = z5 – c5  =  (0 ∙ 1 + 0 ∙ 0)  – 0  = 0 ;

6 = z6 – c6  =  (0 ∙ 0 + 0 ∙ 1)  – 0  = 0 ;

Таб. 2. Математическое программирование – задачи линейного программирования

madgicbox.com - основы математического программирования т2

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

  1. Переход к новому оптимальному плану.

Поскольку проверяемое решение не является оптимальным, найдем другое опорное решение, «улучшающее» значение целевой функции.

В целевой строке таб. 2 имеются отрицательные оценки. Максимальная по модулю среди них –  ∆3 = -40, но примем в качестве вводимой переменной х4.

Если вводимая в базис переменная – это  х4, то решение можно представить в виде:

x5 = 90 — 1·0 + 3·0 + 8·0 + 4· х4 = 90 — 4х3

х6 = 80 — 2·0 + 2·0 + 1·0 + 3· х4 = 80 — 3х4

Отсюда следует, что:

х41 = 22,5

х42  = 26,67

Выполненные расчеты показывают, что х5 обращается в ноль при минимальном значении   х4 = 22,5. Остальная базисная переменная   х6  при  этом  сохраняют  положительные  значения х6 = 80 — 1·22,5 = 57,5. Следовательно, при введении в число базисных переменной х4  в разряд свободных перейдет ( т.е обратится в ноль) переменная  х5 что найдет отражение в таб.3 Математическое программирование – задачи линейного программирования.

Таб. 3. Математическое программирование – задачи линейного программирования

madgicbox.com - основы математического программирования т3

Так, элементы второй строки таб. 3 получены из соответствующих элементов таб. 2 следующим образом:

80 – 90·0,75 = 12,5    2 — 1·0,75 = 1,25         2 — 3·0,75 = -0,25

1 — 8·0,75 = -5 3 — 4·0,75 = 0  0 — 1·0,75 = -0,75        1 – 0 = 1

целевой строки:

0 — 90·( — 7,5) = 675    — 10 — 1·( — 7,5) = -2,5  — 20 — 3·( — 7,5) = 2,5

— 40 — 8·( — 7,5) = 20    — 30 — 4·( — 7,5) = 0      0 — 1·( — 7,5) = 7,5

0 — 0·( — 7,5) = 0

Поскольку среди оценок таблицы 3 еще имеется отрицательная ∆1= -2,5, то делаем вывод о том, что новое решение не является оптимальным.   Переменная х1 теперь вводимая, получим:

Таб. 4. Математическое программирование – задачи линейного программирования

madgicbox.com - основы математического программирования т4

Итого, оптимальный план будет иметь вид:

х1 = 10; х2 = 0; х3 = 0; х4 = 20; х5 = 0 и х6 = 0 что говорит нам, что мы полностью используем ресурсы; Fmax = 700 долларов.

1.2 Фирма может увеличить время работы станков до 100 ч в день, арендуя оборудование, что обойдется в 40 долл. в день.

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

х4 = 20 + 0,4·Δb1         Δb1 ≥ -50

х1 = 10 – 0,6·Δb1         Δb1 ≤ 16,67

F = 700 + 20·Δb1

Предел устойчивости будет выглядеть следующим образом:

40 ≤ Δb1 ≤ 106,67

Таким образом если фирма может увеличить время работы станков до 100 ч в день, при этом приращение времени составит 10 ч в день, так как указанное время входит в предел устойчивости, В указанном пределе устойчивости прибыль на увеличения ресурса 1 составит 6 долларов.

Фирма же должна заплатить 40 долларов за 10 часов дополнительного времени, при этом один час составит 4 доллара.

Новая прибыль составит + 20 долларов.

 1.4 Беспорядки на заводе одного из потребителей приводят к тому, что дневной выпуск изделия IV должен быть сокращен до 15 единиц. Воспользуйтесь двойственным симплекс-методом для составления нового производственного плана.

Введем дополнительное ограничение: х4 ≤ 15 ед.

При этом итоговая таб. 4 примет следующий вид:

Таб. 4. Симплекс таблица, при учете дополнительного ограничения х4 ≤ 15 ед

madgicbox.com - Математическое программирование т4.1

Итого, оптимальный план будет иметь вид:

х1 = 11,25; х2 = 6,25; х3 = 0; х4 = 15; х5 = 0, х6 = 0 и х7 = 0 что говорит нам, что мы полностью используем ресурсы; Fmax = 687,5 долларов.

Сравнив новый оптимальный план выпуска с ограничением х4 ≤ 15, с предыдущим планом, без ограничения можно, говорит, что при жестком ограничении в 15 изделий х4, мы теряем 2,5 доллара на одной выпускаемой единице продукции. Наша новая прибыль сократится на 12,5 долларов и составит теперь 687,5 долларов.

Таким образом, математическое программирование помогло найти оптимальный план производства, который полностью использует ресурсы и выпускает продукцию с максимальным эффектом.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *