48-1. Симплекс-метод решения злп: проверка плана на оптимальность.

Критерием оптимальности рассматриваемого плана является выполнение условия

Возможны три случая:

1. Все оценки тогда найденный базисный план оптимален.

2. Для некоторого j оценка и все элементысоответствующего столбцанеположительные,. В этом случае задача неразрешима, те целевая функция не ограничена на множестве допустимых планов(z стремится к бесконечности)

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

49. Симплекс-метод решения злп: переход к новому плану.

1.  Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец, с минимальным значением С_j(пусть это k-й столбец)

2. Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки): рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. A_i,k>0; для всех этих элементов находим отношениеB_i/A_i,kи выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка); соответствующая i-я переменнаяX_iвыводится из базиса; при нескольких одинаковых отношениях берем любую строку; элементA_i,kназывается разрешающим элементом.

3.  Пересчитать симплекс-таблицу: составляем новую симплекс-таблицу заменив в составе базисных переменных X_iнаX_k; заполняем сначала новую k-ю строку, записывая в нее элементы старой i-ой строки, поделенные на разрешающий элемент; после заполнения k-ой строки заполняем оставшиеся строки; для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).

50. Метод искусственного базиса (м-задача)

Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу: max{F(x)=∑c_ix_i|∑a_jix_i=b_j, j=1,m; x_i≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» R_j следующим образом: ∑a_jix+R_j=b_j, j=1,m;F(x)=∑c_ix_i-M∑R_j

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c_ix_i, , а другая – для составляющей M ∑R_j

51. Транспортная задача. Математическая постановка задачи.

Для построения математической модели задачи необходимо ввести m·nштук переменных

 х_ij, i= 1,…, n, j= 1, …, m,каждая переменнаях_ijобозначает объем перевозок из пунктаA_i в пунктВ_j.Набор переменныхX = {x_ij}и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид: