Задачи линейного программирования. (Тема 3)

Июль 22, 2022

Главная
Информатика
Задачи линейного программирования. (Тема 3)

Содержание

2. Для задач линейного программирования характерно наличие следующих 3-х компонентов: целевая функция; система ограничений; ограничения на знак
3. если он удовлетворяет ограничениям (2) и (3). называется допустимым планом ЗЛП, Вектор Вектор называется оптимальным планом
4. Формы записи ЗЛП 1) Развёрнутая форма записи:
5. 2) Матричная форма записи ЗЛП: (1) (2) (3) 3) Векторная форма записи ЗЛП:
6. Каноническая форма записи ЗЛП (1) (2) В системе ограничений стоят знаки только равенства. (3) (4) В
7. Приведение ЗЛП к канонической форме 1) max z’=-z, 2) Если в ограничении стоит знак то к
9. Скачать презентацию

Слайд 2

Для задач линейного программирования характерно наличие следующих 3-х компонентов:
целевая функция;

система ограничений;
ограничения на знак переменных

ЗЛП – это задача следующего вида:

(1)

(2)

(3)

Уравнение (1) – это целевая функция, а (2) и (3) – это система ограничений.

Слайд 3

если он удовлетворяет ограничениям (2) и (3).
называется допустимым планом

ЗЛП,

Вектор

Вектор

называется оптимальным планом ЗЛП,

если он является допустимым и обеспечивает минимум или максимум целевой функции.

Множество всех допустимых планов ЗЛП образует область допустимых значений (ОДЗ).

Слайд 4

Формы записи ЗЛП
1) Развёрнутая форма записи:

Слайд 5

2) Матричная форма записи ЗЛП:
(1)
(2)
(3)
3) Векторная форма записи

ЗЛП:

Слайд 6

Каноническая форма записи ЗЛП
(1)
(2)
В системе ограничений стоят знаки

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

(3)

(4)

В системе ограничений присутствует выделенный исходный базис.

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

Слайд 7

Приведение ЗЛП к канонической форме
1) max z’=-z,
2)
Если в ограничении

стоит знак

то к левой части ограничения до-

бавляем дополнительную переменную со знаком “+”(

3) Если

не указано, то

Пункты (4) и (5) означают поиск в системе ограничений исходного опорного решения.

Если в ЗЛП нет опорного решения, то такая задача не имеет решений по причине несовместности системы ограничений.

ЗЛП может не иметь решения по двум причинам:

1) система ограничений несовместна;

2) целевая функция не ограничена на ОДЗ.