Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Общий вид задачи линейного программирования.

Линейное программирование – это математическая дисциплина, которая изучает методы нахождения min или max значения линейной функции нескольких переменных при условии, что все эти переменные удовлетворяют конечному числу линейных уравнений и неравенств.

Задача линейного программирования:

Функция цели: Z = c₁x₁+c₂x₂+…+c_nx_n => min (max)

@ - любое равенство или неравенство.

a₁₁x₁+…+a_1nx_n@b₁

.......................

a_m1x₁+…+a_mnx_n@b_n, x₁>=0,..., x_n>=0.

Каноническая форма представления задач линейного программирования. (2)

Линейное программирование – это математическая дисциплина, которая изучает методы нахождения min или max значения линейной функции нескольких переменных при условии, что все эти переменные удовлетворяют конечному числу линейных уравнений и неравенств.

Z = c₁x₁+c₂x₂+…+c_nx_n => max

a₁₁x₁+…+a_1nx_n = b₁

.......................

a_m1x₁+…+a_mnx_n = b_m, x₁>=0,..., x_n>=0.

Только равенства.

Ограничения в задачах линейного программирования, перевод задач линейного программирования в каноническую форму. (2)

Линейное программирование – это математическая дисциплина, которая изучает методы нахождения min или max значения линейной функции нескольких переменных при условии, что все эти переменные удовлетворяют конечному числу линейных уравнений и неравенств.

Ограничения в виде неравенств можно преобразовать в равенство. Для этого вводится x_n+1:

a_i1x₁+a_i2x₂+...+a_inx_n+b_i>=0, отсюда:

a_i1x₁+a_i2x₂+...+a_inx_n+b_i= x_n+1, x_n+1>=0.

Для того, чтобы наложить условие неотрицательности необходимо вместо одной переменной, например xi, заменить на две переменные: x_i^’>=0 и x_i­^’’>=0, отсюда x_i= x_i^’- x_i^’’.

Возможно и обратное! Любую задачу линейного программирования можно сформулировать таким образом, чтобы все ограничения были в виде неравенств.

Понятия допустимого, оптимального решения, линейной формы задач ЛП. (2)

Любое неотрицательное решение в данной задаче (в задаче ЛП) называется допустимым решением, а вот допустимое решение, которое дает min или max целевой функции называется оптимальным решением. Оптимальное решение не обязательно является единственным и не обязательно оно вообще существует. Саму целевую функцию иногда называют линейной формой. Суть задач ЛП: из множества допустимых решений выбрать то, которое обращает линейную форму в min или max.

Геометрическая интерпретация задач линейного программирования. (2)

Любую задачу линейного программирования можно представить геометрически. Для этого все ограничения лучше записать в виде неравенств:

a_i1x₁+a_i2x₂+…+a_inx_n>=b_i

(полупространство, все переменные лежат по одну сторону от плоскости)

Ω

В итоге мы получаем некое пересечение множеств, которое образует в пространстве выпуклый многогранник. Значение целевой функции z в произвольной точке х^’ можно рассматривать, как уклонение точки х^’ от плоскости z=0.

Получаем геометрический смысл задач ЛП – это отыскание в полученном многограннике Ω тех точек, которые наименее или наиболее удалены от плоскости z=0.

Понятие базисных и свободных переменных. (2)

Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом (для симплекс - метода).

Клетки таблицы ненулевые называются базисными клетками и соответствующие переменные – базисные переменные. Остальные клетки называются свободными, которые составляют опорное решение (для транспортной задачи).