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

     Задание 1

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

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

     Максимизация  прибыли достигается в точке  максимума функции:

  , при выполнении  следующих условий: 
 
 

     Подставив значения, имеем: 
 
 
 

     Решим задачу симплекс-методом, используя  средства Microsoft Excel. На выходе получаем: 

Решение симплекс-методом:

1. Приведем задачу к канонической форме (в систему уравнений) и введем дополнительные переменные x₃, x₄, x₅  для реализации шага:

2. Построим  исходную симплекс-таблицу:

  Таким образом, в данном базисном решении неосновные переменные x₁=x₂=0. Базисные переменные: x₃ = 918, x₄ = 918, x₅ = 783. Данное базисное решение является допустимым.

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

3. Проверка условия: все c_j ≤ 0.

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

   В нашей задаче последняя строка содержит два положительных элемента, значит задача не решена.

4. Выбор разрешающего столбца (переменной, вводимой в базис).

 Разрешающий  столбец выбирается в соответствии  со следующим условием:

   где r - номер разрешающего столбца.

   В нашем  случае:  
 

5. Проверка условия: все a_ir ≤ 0.

   Все элементы разрешающего столбца x₂ положительны (12;5;11), значит, задача имеет решение.

6. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

где s - номер  разрешающей строки.  
 

В нашем случае: 

т.е. исключать  из базисного решения будем переменную x₅.

      Элемент, стоящий на пересечении разрешающей  строки и разрешающего столбца, называется разрешающим элементом. В нашем случае a_sr=11.

7. Пересчет элементов симплекс-таблицы (переход к новому базисному решению).

Для элементов разрешающей  строки используются следующие формулы:  

где s - номер разрешающей строки,

   r - номер разрешающего столбца,

   a’_sj,b’_s - новые значения пересчитываемых элементов,

   a_sj, b_s - старые значения пересчитываемых элементов,

   a_sr - старое значение разрешающего элемента.

Элементы разрешающего столбца: 

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

   Таким образом, в новом базисном решении  базисными переменными являются: x₂ = 71,182, x₃ = 638,818, x₅ = 562,091 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x₁=x₅=0. Значение целевой функции в этом случае равно 284,727 (значение можно видеть в правой нижней ячейке таблицы).

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

Решение графическим методом:

1. Построим графики функций и выделим ОДР – серый треугольник.
2. Построим вектор А, задающий направление вектора (2;4).
3. Перпендикулярно вектору A проводим линию уровня L=0 через 0(0;0).
4. Параллельным перемещением прямой L=0 находим крайнюю точку, в которой функция L достигает оптимума – точка М.
5. Найдем координаты оптимальной точки:

6.Оптимальное значение целевой функции:

А

М

Задание 2.

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

Вариант 3

Решение.

     Задача  имеет закрытый тип, т.к. запасы груза  18+18+18+18 =72 равны суммарным потребностям магазинов 14+14+14+16+14 = 72.

     Составим  опорный план по правилу минимального элемента.

     Введем  некоторые обозначения: A’_i - излишек нераспределенного груза от поставщика A_i, B’_j - недостача в поставке груза потребителю B_j.

     Находим незанятую клетку с минимальным  тарифом: (1,3). Помещаем туда меньшее из чисел A’₁=18 и B’₃=14.

     Находим незанятую клетку с минимальным  тарифом: (3,1). Помещаем туда меньшее из чисел A’₃=18 и B’₁=14.

     Находим незанятую клетку с минимальным  тарифом: (1,4). Помещаем туда меньшее из чисел A’₁=4 и B’₄=14.

     Находим незанятую клетку с минимальным  тарифом: (2,2). Помещаем туда меньшее из чисел A’₂=18 и B’₂=14.

     Находим незанятую клетку с минимальным  тарифом: (3,5). Помещаем туда меньшее из чисел A’₃=4 и B’₅=14.

     Находим незанятую клетку с минимальным  тарифом: (2,4). Помещаем туда меньшее из чисел A’₂=4 и B’₄=12.

     Находим незанятую клетку с минимальным  тарифом: (4,4). Помещаем туда меньшее из чисел A’₄=18 и B’₄=8.

     Находим незанятую клетку с минимальным  тарифом: (4,5). Помещаем туда меньшее из чисел A’₄=10 и B’₅=10. 
 
 
 
 
 
 
 
 
 

     Получаем  заполненную таблицу:

Транспортные  расходы составят: Z = 206.

     Решим задачу методом потенциалов. Т.к. m+n-1=8 и имеем 8 загруженных клеток, план ацикличный. Пусть U_i и V_j - потенциалы i-го склада и j-го магазина соответственно.

     Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j, просматривая все занятые клетки. Получим:

U₁ = 0

U₂ = C_2,4-V₄ = 5 – 2 = 3

U₃ = C_3,5-V₅ = 3 – 4 = -1

U₄ = C_4,4-V₄ = 5 - 2 = 3 
 

V₁ = C_3,1-U₃ = 1 + 1 = 2

V₂ = C_2,2-U₂ = 2 – 3 = -1

V₃ = C_1,3-U₁ = 1 – 0 = 1

V₄ = C_1,4-U₁ = 2 – 0 = 2

V₅ = C_4,5-U₄ = 7 – 3 = 4

     Для свободных клеток определим значения оценок (разностей между прямыми  и косвенными тарифами):

S_1,1 = C_1,1 – (U₁+V₁) = 0

S_1,2 = C_1,2 – (U₁+V₂) = 8

S_1,5 = C_1,5 – (U₁+V₅) = 1

S_2,1 = C_2,1 – (U₂+V₁) = 3

S_2,3 = C_2,3 – (U₂+V₃) = 5

S_2,5 = C_2,5 – (U₂+V₅) = 2

S_3,2 = C_3,2 – (U₃+V₂) = 19

S_3,3 = C_3,3 – (U₃+V₃) = 4

S_3,4 = C_3,4 – (U₃+V₄) = 5

S_4,1 = C_4,1 – (U₄+V₁) = 2

S_4,2 = C_4,2 – (U₄+V₂) = 7

S_4,3 = C_4,3 – (U₄+V₃) = 17 

     Опорный план является оптимальным, так все  оценки свободных клеток удовлетворяют  условию U_i + V_j ≤ C_i,j.

     Минимальные затраты составят: