Исходная задача

Двойственная задача

у₁, у₂ – произвольные по знаку.

Решив двойственную задачу графическим методом, получим

, при этом

По 1-й теореме двойственности

Подставим в систему ограничений двойственной задачи:

3=3,

1=1,

-21/2<3 ,

-3<1

Так как х₃ = х₄ = 0, то система исходной задачи примет вид

Решая данную систему, получим , при этом

Рассмотрим решение задач с использованием обратной матрицы.

Пусть решение исходной задачи , при этом

Решение двойственной задачи найдём по формуле где

, , = .

Таким образом, , .

Решение смешанных двойственных задач

Смешанные двойственные задачи можно решать с использованием теорем двойственности.

Исходная задача

Двойственная задача

у₁ – произвольная по знаку,

у₂

Найдём оптимальное решение двойственной задачи, решив сначала исходную симплексным методом:

, при этом

По 1-й теореме двойственности

Так как х₁ > 0, x₃ > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств: ,

откуда у₁ = -5/3, у₂ = 4/3, т. е.

Лекция 6

5. Транспортная задача

5.1. Общая постановка задачи

В общем виде задачу можно представить следующим образом: в т пунктах производства А₁, А₂, …, А_т имеется однородный груз в количестве соответственно а₁, а₂, …, а_т. Этот груз необходимо доставить в п пунктов назначения В₁, В₂, …, В_п в количестве соответственно b₁, b₂, …, b_n. Стоимость перевозки единицы груза (тариф) из пункта А_i в пункт В_j равна с_ij.

Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость.

Определение 1. Если , то задача называется закрытой. Если , то открытой.

Обозначим через х_ij количество груза, перевозимого из пункта А_i в пункт В_j. Рассмотрим закрытую транспортную задачу. Её условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.

Таблица 5.1

B j Ai	B1	B2	…	Bj	…	Bn
	b1	b2	…	bj	…	bn
A1 a1	c11 x11	c12 x12	…	c1j x1j	…	c1n x1n
A2 a2	c21 x21	c22 x22	…	c2j x2j	…	c2n x2n
…	…	…	…	…	…	…
Ai ai	ci1 xi1	ci2 xi2	…	cij xij	…	cin xin
…	…	…	…	…	…	…
Am am	cm1 xm1	cm2 xm2	…	cmj xmj	…	cmn xmn

Математическая модель закрытой транспортной задачи имеет вид

при ограничениях:

Оптимальным решением задачи является матрица

,

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

- нахождение исходного опорного решения;

- проверка этого решения на оптимальность;

- переход от одного опорного решения к другому.