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


Постановка задачи

В общем виде задача линейного программирования записывается следующим образом:

Дано:

1. Множество переменных (неизвестных) задачи

для

- вектор столбец переменных (неизвестных) задачи

2. Множество допустимых решений задачи Q (система условий задачи), задаваемое в виде системы линейных ограничений

a11·x1 + … + a1j·xj +…+ a1n·xn = b1

…………………………………..

ai1·x1 + … + aij·xj +… + ain·xn = bi

…………………………………..

Q=
ak1·x1 + … + akj·xj+… + akn·xn = bk


ak+1 1·x1 + … + a k+1 j·xj+…+ a k+1 n·xn≤ b k+1

…………………………………..

am1·x1 + … + amj·xj+ … + amn·xn≤ bm

xj≥0 для

 

3. Функционал задачи (линейная форма задачи)

F(x)=f1·x1 + … + fj·xj+… + fn·xn

F(x)=f·x,

где

f=(f1, f2, … fj, … , fn) – вектор строка коэффициентов функционала.

4. Матрица условий задачи

5. Вектор столбец правой части ограничений

6. Матричная форма задачи оптимизации

Q=

Если ищется максимум функционала

Найти: такое, что

Если ищется минимум функционала

Найти: такое, что

Область Q, заданная системой линейных уравнений и неравенств, представляет собой выпуклый многогранник в n-мерном пространстве, а экстремум линейной функции достигается в его вершинах.

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

.

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

.

В функционал задачи переменные войдут с нулевыми коэффициентами.

Во всех случаях, когда задача линейного программирования разрешима, ее решение сводится к упорядоченному перебору вершин n-мерного многогранника.



Дата добавления: 2021-05-28; просмотров: 326;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.