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

Далее эту задачу с двумя переменными можно решать или графоаналитически или в EXCEL.

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

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

Геометрический смысл тот же, что и в п.1 (для задачи в каноническом виде).

Вершины многогранника называются угловыми точками.

Множество решений системы (1) является выпуклым многогранником (напомним, что выпуклое множество вместе с любыми двумя точками содержит все точки содиняющего их отрезка).

Система (1) имеет бесконечное множество решений и целевая функция ограничена на множестве допустимых решений. Именно такой случай экономически представляет наибольший интерес. Последний случай рассмотрим более подробно. Итак, имеет место последняя ситуация.

Система (1) имеет бесконечное множество решений, но целевая функция не ограничена на множестве допустимых решений. Экономически такой случай не интересен.

Система (1) имеет единственое решение. Ясно, что оно и будет оптимальным решением.

Система (1) не имеет решений. Интерес такая ситуация не представляет.

В- столбец правых частей, с- строка коэффициентов целевой функции.

Какие возможны ситуации?

Теоретические основы линейного программирования (без доказательства).

3. Оптимальное решение достигается хотя бы в одной угловой точке. Отсюда, принципиальный путь поиска оптимального решения: перебрать все угловые точки (их конечное число!) и среди них выбрать ту в которой целевая функция достигает максимума.

2. Задача линейного программирования в стандартной форме

а₁₁х₁ + а₁₂х₂+……а_1nх_n ≤ в₁

а₂₁х₁ + а₂₂х₂+……а_2nх_n ≤ в₂ (2)

……………………………

а_m1х₁ + а_m2х₂+…а_mnх_n ≤ в_m

x_i ≥ 0, i = 1,n

F = c₁х₁ + c₂х₂+……c_nх_n → max

Пример:

Участок цеха выпускает изделия двух видов. Исходные данные указаны в таблице стандартного вида:

Пусть х₁, х₂ количество изделий каждого вида, соответствено.

5х₁ + 3х₂ ≤ 45 (3)

х₁ + 2х₂ ≤ 16 (4)

х₁, х₂ ≥ 0

F = 2x₁ + 3x₂ → max

Систему ограничений в стандартной форме перепишем так:

Множество допустимых решений заштриховано на рис. Среди точек этого многоугольника и нужно выбрать оптимальную.

Выше мы отметили, чио опт. точка совпадет с угловой точкой (О,А,В,С). Чтобы их не перебирать поступим так:

Изобразим линию уровня F=0 и отметим в точке О вектор- градиент. Из курса высшей математики мы знаем, что он ортогонален линии уровня и указывает направление возрастания целевой функции F. (нам это и нужно- прибыль).