Метод решения задач линейного программирования

1) Найти вершины области допустимых решений как точки пересечения ограничений.

2) Определить последовательно значения целевой функции в вершинах.

3) Вершина, в которой целевая функция приобретает максимальное значение, является оптимальное решение.

4) Координаты оптимальной вершины есть оптимальные значения искомых переменных

 

Симплекс метод --метод последовательного улучшения плана (метод Данцига)

Алгоритм симплекс- метода:

1)Находят начальный базис и связное с ним допустимое решение.

2)Пошаговое вычисление целевой функции, в направлении непрерывного возрастания её.

 

Задачи ЛП:

1.

Требуется найти план выпуска продуктов: А,В.С. Д.

Ресурсы:

-Трудовые

-материальные

-финансовые.

 

i– тый ресурс для производства каждого j – го продукта имеет норму расхода а (i, j).

Количество каждлго вида ресурса в наличии обозначают b (i)

Таблица 1

Ресурсы Продукты

А, В. С. Д. Наличие в

Удельные нормы расхода запасах

-Трудовые 6 4 2 1 800

-материальные 7 9 11 5 2 000

-финансовые 3 4 5 6 12 000

 

Ограничения

Нижнее 1 - 3 - -

Верхнее 12 2 - - -

-------------------------------------------------------------------------------------------------------------------------------------------

План х1 х2 х3 х4

 

Обозначим:

F – ресурсы

R – результат их применения

 

При заданных зависимостях результата и потребных ресурсов от количества выпускаемой продукции R = R(x (j)), F = F (x(j)) обе постановки распределения ресурсов в сокращённой форме:

 

L(1) = R (x(j)) →max L(2) = F (x(j)) → min

F(x(j)) ≤ F * F(x(j)) ≤ F *

R (x(j) ≥ R*

 

где F*, R* заданные плановые величины ресурсов и результата

Пусть для продукции А, В, С, Д прибыль от реализации единицы продукции каждого вида составляет 5,6, 7 и 8 д.е. соотвественно, а суммарная прибыль от всего производства должна быть не менее 3000 д.е.

 

Тогда математическая модель задачи с учётом данных таблицы 1:

 

мax L(1) = 5x(1) + 6x(2) + 7x(3) + 8 x(4)

6x (1) + 4x(2) + 2x(3) + x(4) ≤ 800

7х(1) + 9х(2) + 11х(3) + 5 х(4) ≤ 2000

3х(1) + 4х(2) + 5х(3) + 6х(4) ≤ 12000

 

1 ≤ х(1) ≤ 12, х(2) ≤ 2, х(3) ≤ 3, х(4) ≥ 0.

Мах L (1) = 3162

 

Задача 2.Рассмотрим: х2

х1 + 4х2 ≤ 14 |

3х1 + 4х2 ≤ 18 |

6х1 + 2х2 ≤ 27 |

х1, х2 ≥ 0 |

|

|

|

|

|

|

|

!,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,х1

 

 

Оптимальное решение – координаты вершины области допустимых решений

 

Нелинейное программирование

решаются методом кусочно – линейной аппроксимации, или метода множителей Лагранжа.Общего метода решения нет.

Задача

Надо изготовить 180 изделий

На первом предприятии затраты на х изделий равны [ 4* х(1) + х(1) ]

На втором [ 8 х(2) + 6 х (2) ]

 

Сколько изделий изготовить на каждом предприятии, чтобы общие затраты были минимальны?

 

Общая постановка

Max f (x(1), x(2), …, x(n)); (1)

g(i) [x(1), x(2), …, x(n) ] = b(i), (i = 1,…,m). (2)

 

Введём набор переменных λ(1), λ(2),,…, λ(m) - множители Лагранжа.

Составляем функцию Лагранжа

F (x(1), x(2), …, x(n), λ(1), λ(2),,…, λ(m)) =

(3)

= f (x(1), x(2), …, x(n) + ∑ λ(i) * [ b (i) – g (i) [ x(1), x(2), …, x(n)]

Находим частные производные

∂ F ∂ F

---------- (j = 1,…,n); ------- (i = 1,…,m)

∂ x (j) ∂ λ(i)

 

Рассматриваем систему n + m уравнений

∂ F m ∂ g(i)

--------- = ∑ λ(i) * --------

∂ x (j) i ∂ x(i) (4)

 

∂ F

------ = b (i) – g (i) [ x(1), x(2), …, x(n)]

∂ λ(i)

 

 

Продолжение решения задачи:

2 2

Min f = 4 x(1) + x(1) + 8 x (2) + x(2) (5)

 

x(1) + x(2) = 180 (6)

 

x(1),x(2) ≥ 0 (7)

Функция Лагранжа для этого примера:

2 2

F (x1,x2, λ) = 4x(1) + x(1) + 8 x(2) + x(2) + λ (180 – x (1) – x (2))

Вычисляем частные производные по х(1), х(2), λ и приравниваем их «0».

 

 

∂ F

-------- = 4 + 2х(1) – λ =0

∂ x (1)

∂ F

--------- = 8 + 2х (2) – λ =0 }

∂ x (2)

 

∂ F

------ = 180 – x(1) – x (2) = 0, отсюда (8)

∂ λ

4 + 2х(1) = 8 +2х(2) или х(1) + х(2), решая совместно (8) получаем

х(1)опт = 91, х(2) опт = 89

Используя вторые частные производные, убеждаемся, что в этой точке функция f имеет минимум

 

Задание:

Надо изготовить 200 изделий

На первом предприятии затраты на х изделий раны 4* х(1)

На втором 20 х(2) + 6 х (2))

 

Сколько изделий изготовить на каждом предприятии, чтобы общие затраты были минимальны?

 

 

Имитационное моделирование

Требования к имитационной модели:

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

-проста и понятна пользователю,

-гарантирует отсутствие абсурдных ответов,

-полна по возможностям решения главной задачи,

-позволяет обновлять данные,

-допускает постепенное усложнение или изменение последовательности решения.

Этапы процесса моделирования:

1. Описание проблемы

2. Анализ системы – установление границ, ограничений и показателей эффективности системы.

3. Конструирование модели – логической схемы.

4. Отбор данных для построения модели.

5. Описание модели на языке EXEL.

6. Оценка адекватности модели реальной системе.

7. Планирование эксперимента.

8. Серия испытаний – алгоритм проведения расчётов.

9. Имитация и оценка чувствительности.

10. Выводы о результатах моделирования