Разработка урока по математике на тему: "Формы записи задач линейного программирования. Понятие о базисном решении."

«Математика»

Ход занятия

Повторение:

1. Записать на доске экономико-математическую модель ЗЛП на максимум.

2. Записать на доске экономико-математическую модель ЗЛП на минимум.

3. Дать понятие экономико-математической модели.

4. Что называется оптимальным решением?

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

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

Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции при выполнении условий

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

Так как общая задача ЛП имеет ограничения не только вида «=», но и «≤», «≥», а целевая функция может либо максимизироваться, либо минимизироваться, то необходимо уметь приводить любые задачи ЛП к канонической форме. Рассмотрим 2 частных вида задач ЛП.

1 вид.

f=c₁x₁+c₂x₂+…+c_nx_n→max;

х_j ≥0 (j= ) b_i≥0 (i= )

Левая часть каждого ограничения данной задачи меньше либо равно правой. Для их уравнивания необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные х_n+1, х_n+2, …, х_n+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить её значение.

После приведения к канонической форме задача будет иметь вид:

f=c₁х₁+…+c_nx_n+0·x_n+1+0·x_n+2+…+0·x_n+m→ max

х_j ≥0 (j= ) b_i≥0 (i= )

Переменные х_n+1, х_n+2, …, х_n+m называются дополнительными.

2 вид

f=c₁х₁+c₂x₂₊…+c_nx_n → min

х_j ≥0 (j= ) b_i≥0 (i= )

Определение min значения целевой функции f можно свести к определению максимального значения функции (-f), так как min f = -mах (-f)

После приведения к канонической форме задача будет иметь вид.

f=-c₁х_1-…-c_nx_n+0·x_n+1+0·x_n+2+…+0·x_n+m→ max

х_j ≥0 (j= )

Таким образом, если в задаче ЛП определяется минимум целевой функции, то такую задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения вида «≥» и «≤» привести к ограничениям – равенствам.

Понятие о базисном решении.

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

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

Первое решение задачи, полученное таким образом, называется исходным базисным решением.

Базисное решение называется вырожденным, если значение одной или нескольких базисных переменных равны нулю. Задача, имеющая хотя бы одно вырожденное базисное решение, называется вырожденной, в противном случае – невырожденной.

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

В каждое ограничение задачи вводится соответственно искусственные неотрицательные переменные, которые принимаются в качестве базисных. Искусственные переменные входят в целевую функцию задачи с коэффициентом (-М), где М – большое положительное число, во много раз больше заданных в условии задачи.

После ввода искусственных переменных задача принимает вид

f=-c₁x₁-c₂x₂-…-c_nx_n+0·x_n+1+0·x_n+2+…+0·x_n+m-Mx_n+m+1-Mx_n+m+2-…-Mx_n+m+mmax

х_j ≥0 (j= )

Пример 1.

Привести к канонической форме следующую задачу ЛП и найти исходные базисные решения.

f=2x₁+x₂-x₃→max

x₁0, x₂0, x₃0

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

Каноническая форма будет иметь вид.

f=2x₁+x₂-x₃+0·x₄+0·x₅→max

х_j ≥0 (j= )

Только одна переменная х₅ входит в систему ограничений с коэффициентом 1 и только в одно второе уравнение, следовательно, она является базисной переменной, а в первом и в третьем ограничениях базисных переменных нет. Поэтому введем в них искусственные базисные переменные х₆ и х₇. В целевую функцию эти переменные войдут с коэффициентом (-M). Получим

f=2x₁+x₂-x₃+0·x₄+0·x₅-Mx₆-Mx₇→max

х_j ≥0 (j= )

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

х₁=0, х₂=0, х₃=0, х₄=0

Тогда значения базисных переменных: х₅=9, х₆=4, х₇=10. Подставив значения базисных переменных в целевую функцию, получим величину

f=-М·4 - М·10= -14M.

Домашнее задание выполнить задания

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

а) f = 3х₁ + 4х₂ ® mах

х₁ ³ 0, х₂ ³ 0

б) f = -3х₁ + 2х₂ + 5х₃ +3х₄ х₅ ® mах

в) f = 2х₁ - 3х₂ + 2х₄ + 3х₅ ® mах

г) f = 2х₁ + х₂ + х₃ ® min

х₁  0, х₂  0, х₃ 0

д) f = х₁ - х₂ - 2х₃ - 3х₄ ® min

е) f = х₁ + х₂ ® mах

х₁ ³ 0, х₂ ³ 0