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

Если оценки всех свободных векторов-столбцов не равны нулю, найденное оптимальное решение единственно.

4) Если оптимальное решение не найдено, ищем новое опорное решение.

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

ЗЛП не имеет решения в силу неограниченности целевой функции, если какой-нибудь столбец коэффициентов свободной переменной, оценка которого противоречит признаку оптимальности, не содержит ни одного положительного элемента.

Если условие отсутствия оптимального решения не выполняется, введём в базис новую переменную, столбец коэффициентов которой имеет оценку, противоречащую признаку оптимальности. Если таких столбцов несколько, выбираем столбец с «наихудшей» оценкой.

Для выбора разрешающего элемента в столбце новой базисной переменной используем условие неотрицательности свободных членов. Из базиса выводится столбец с разрешающим элементом (единицей) в соответствующей строке.

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

Приращение целевой функции при переходе от одного опорного решения к другому можно вычислить по формуле:

Тема 5. 100 баллов. Постановка и основные понятия транспортной задачи.

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

Дано: Несколько (m) поставщиков однородного товара хотят передать этот товар нескольким (n) потребителям. Мощность i го поставщика - равна запасам товара у этого поставщика. Мощности поставщиков заносятся в первый столбец таблицы поставок. Мощность j-го потребителя - - определяется количеством необходимого ему товара. Мощности потребителей равны их запросам. Известна стоимость перевозки единицы товара от каждого из поставщиков к каждому потребителю - .

Задача: Для каждой пары «поставщик-потребитель» определить объём перевозки , то есть составить оптимальныйплан перевозок товара.

Полученная матрица перевозок должна удовлетворять следующим условиям:

1) суммарные затраты на перевозку минимальны;

(Сумма затрат на перевозку равна сумме произведений объёмов перевозок товара на их стоимости )

2) мощности всех поставщиков реализованы;

3) запросы всех потребителей удовлетворены

В транспортной задаче n+m уравнений ограничений, n.m переменных; из них n+m+1 линейно независимых уравнений и n+m+1 базисных переменных (заполненных клеток в таблице поставок). Число свободных клеток n.m – (n+m+1) равно числу свободных переменных задачи.

Необходимое и достаточное условие существования решения транспортной задачи.

Суммарные запасы (мощности) поставщиков и потребителей равны между собой (задача закрыта, или задача с правильным балансом).

Цикл клетки (i, j) – последовательность клеток таблицы ТЗ, определяемая ломаной линией, состоящей из вертикальных и горизонтальных звеньев. Начало и конец ломаной – в клетке (i, j), остальные вершины – в заполненных клетках таблицы.

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

Алгоритм решения ТЗ,

1) находим начальное базисное допустимое (опорное) решение, состоящее из (n+m+1) заполненных клеток таблицы поставок методом северо-западного угла или методом минимальной стоимости. Убеждаемся в его «опорности» методом вычёркивания рядов с одной заполненной клеткой из матрицы поставок.

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

3) если найденное решение не оптимально, изменяем его, используя « сдвиг по циклу »: увеличиваем объём перевозок во всех нечётных клетках цикла и уменьшаем во всех чётных на величину ( равен наименьшему из объёмов перевозок в чётных клетках цикла). Переходим к пункту 2).

Построение начального решения:

В клетку (i, j) таблицы поставок вносим максимально возможный объём перевозки, равный оставшимся запасам i-го поставщика или неудовлетворённым потребностям j -го потребителя. Затем вычёркиваем из таблицы поставщика или потребителя, потребности которого полностью удовлетворены. (одна заполненная клетка таблицы – один вычеркнутый ряд матрицы).

Метод северо-западного угла: последовательнозаполняем правую верхнюю клетку таблицы поставок.

Метод минимальной стоимости – в первую очередь заполняем клетки с наименьшей стоимостью первозки.

⇐ Предыдущая 12