14. Метод искусственного базиса.

Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу: 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Рассмотрим процедуру решения задачи на конкретном примере.

15. Транспортная задача. Постановка задачи и ее математическая модель.

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.^[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (производства) в n пунктов назначения (потребления) . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j-м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

Составим математическую модель задачи. Найти наименьшее значение линейной функции

(12.1)

при условиях

(12.2)

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

Таблица 12.1

Пункты отправления	Пункты назначения					Запасы
				…
				…
				…
…	…	…	…	…	…		…
				…
Потребности				…