Прямая задача

n

max L (1) = ∑ c(j)* x (j), при ограничениях

j= 1

x (j) ≥ 0 (мир решений – реален).

n

∑ a(i,j) * x (i) ≤ b (i) (i= 1,2, …, m)

j= 1

2) двойственная задача имеет целевую функцию

n

min L (2) = ∑ b(j)* y(j) при условиях:

j= 1

m

∑ a(i,j) * y (i) ≥ c (i) (i= 1,2, …, m), при ограничениях

j= 1

y (j) ≥ 0 - цена единицы ресурса (мир цен – реален);

для выпуска единицы j – го вида продукции необходимо по нормам a (i, j) единиц i- го ресурса

Теоремы линейного программирования:

Линейная система, в которой число неизвестных равно числу уравнений, имеет одно решение

Если число неизвестных меньше числа уравнений, то решения нет и система несовместна

1)Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R -1, то она принимает это значение в крайней точке реального пространства R -1.

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

2)Если задача линейного планирования содержит n переменных и m ограничений

(n ≥ m) в форме неравенств, не считая ограничений неотрицательности

x (j) ≥ 0, то в оптимальное решение входит не более чем m ненулевых компонент вектора x.

При векторной форме записи ограничения задачи ЛП записывают:

А (1) * Х (1) +... + А(n) Х(n) ≤ b.

Поскольку А(1),..., А(n) - m – мерные вектора (n ≥ m), то среди них всегда найдётся m линейно независимых векторов, образующих базис m – мерного пространства и содержащих конус, образованный векторами А(1),..., А(n).

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

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

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

Дата добавления: 2015-10-24