Общая прямая задача линейного программирования — различия между версиями
Строка 50: | Строка 50: | ||
*[[Каноническая задача]]; | *[[Каноническая задача]]; | ||
*[[Производственная задача]]; | *[[Производственная задача]]; | ||
+ | *[[Общая прямая задача линейного программирования]]; | ||
*[[Общая двойственная задача линейного программирования]]; | *[[Общая двойственная задача линейного программирования]]; | ||
*[[Транспортная задача]]; | *[[Транспортная задача]]; |
Версия 17:48, 2 февраля 2016
Общая прямая задача — это задача максимизации с ограничениями всех видов и с переменными всех видов.
Содержание
Обозначения
Введём обозначения:
n – число переменных;
1, 2, .., n1 – номера неотрицательных переменных;
n1+1, n1+2, …, n2 – номера переменных без ограничений;
n2+1, n2+2, …, n – номера неположительных переменных;
m – число ограничений;
1, 2, .., m1 – номера ограничений вида ≤;
m1+1, m1+2, …, m2 – номера ограничений вида =;
m2+1, m2+2,…,m – номера ограничений вида ≥;
aij – коэффициент в i-том ограничении перед j-той переменной;
cj – коэффициент в целевой функции перед j-той переменной;
bi – значение границы в i-том ограничении;
xj – j-тая переменная.
Математическая модель
Математическая модель общей прямой задачи имеет следующий вид:
или
Построение симметричной задачи
Введём дополнительные переменные:
yi – i-тая переменная, i=1, 2, .., m.
Соответствия ограничений и переменных прямой и двойственной задач имеют следующий вид:
Симметричная задача
Математическая модель общей двойственной задачи имеет следующий вид:
Другие задачи:
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Трёхиндексная транспортная задача;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
- Участник:Logic-samara