Решение задач линейного программирования 3 (стр. 2 из 6)
Так же у каждого из судов есть производительность. Она отличается в зависимости от типов судов и от линий. Так же есть заданный объём перевозок(таблица 1). Запишем следующие ограничения:
(2.2)Т.к. нам надо определить такое распределение судов при котором загрузка будет максимальной, то целевая функция будет на максимум.
Исходя из этих данных запишем целевую функцию:
L(x)=
(2.3)Математическая модель задачи будет выглядеть следующим образом
(2.4)3. Обоснование выбора метода решения задачи
Любая задача линейного программирования может быть представлена в канонической и симплексной форме. В симплексной форме задача разрешена относительно базисных переменных.
Анализ задачи в симплексной форме позволяет сделать вывод: если коэффициенты отрицательные, то базисный план соответствует форме задачи линейного программирования, является наиболее оптимальным, поскольку любое изменение небазисных переменных (их увеличение) будет приводить к ухудшению целевой функции.
Достаточное условие оптимальности: если в задаче на максимум коэффициенты целевой функции отрицательны, то соответствующий базисный план оптимален.
В задаче на минимум достаточное условие — неотрицательные коэффициенты целевой функции.
Если хотя бы один из коэффициентов целевой функции в задаче на минимум положителен, на максимум — отрицателен, то целевую функцию можно улучшить, увеличив значения соответствующих базисных переменных.
Для решения задач симплекс-методом необходимо:
a) привести задачу к канонической форме.
b) преобразовать задачу линейного программирования к симплексной форме, т.е. разделить переменные задачи на две группы: базисные и небазисные. Разрешить систему относительно базисных переменных и исключить базисные переменные из целевой функции.
c) Вспомнить одну или более итераций симплекс-метода, которые включают:
(1) проверку достаточных условий оптимальности и выбор ведущей переменной
(2) вычисление максимально допустимого шага вдоль ведущей переменной и выбор разрешающего уравнения
(3) преобразование симплексной формы, связанное с заменой в базисе — переменная, соответствующая разрешающему уравнению, покидает базис, на ее место вводится ведущая переменная.
Рассмотрим задачу линейного программирования в канонической форме:
(3.1)Симплексной формой задачи (3.1) называется такое ее представление, при котором система основных ограничений разрешены относительно m переменных, которые называются базисными.
i1, i2, …, im — индексы базисных переменных.
Тогда система основных ограничений разрешенная относительно базисных переменных будет иметь вид:
(3.2)Jб = {i1, i2, …, im} — базисные переменные
Jн = {j1, j2, …, jm} — небазисные переменные
Jб È Jн = J = {1, 2, …, n}
Используя уравнение системы (3.2) мы можем исключить базисные переменные из целевой функции:
(3.3)xj ³ 0, j = J (3.4) — известные ограничения.
Задачу линейного программирования с целевой функцией (3.3) и ограничениями (3.2) и (3.4) будем называть задачей линейного программирования в симплексной форме, если все свободные члены bi ³ 0,
. 
(3.5)Такой задаче ставим в соответствие базисный план, который состоит из:
Введем дополнительное обозначение:
Задачу (5) можно переписать в следующем виде:
(3.6)1. Симплекс-метод в табличной форме.
Предположим, что задача линейного программирования в канонической форме приведена к симплексной форме (3.6). Перенесем коэффициенты целевой функции вектора свободных членов
и матрицы R, L, в специальную симплексную таблицу: | б\н | B | | … | | … | | … | | |
| | | r | … | r | … | r | … | r | |
| | | | … | | … | | … | | |
| … | … | … | … | … | … | … | … | ||
| | | | … | | … | | … | | |
| … | … | … | … | … | … | … | … | ||
| | | | … | | … | | … | | |
| … | … | … | … | … | … | … | … | ||
| | | | | | |
L 
1 этап: проверяем достаточное условие оптимальности (таблица) базисного плана.