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

     Задание 1

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

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

№
3	6	8	13	12	5	11	918	918	783	2	4

 

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

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

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

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

   
 
 
 
 

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

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

 
 

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

Базис	Переменные					bi
	x1	x2	x3	x4	x5
x3	6	12	1	0	0	918
x4	8	5	0	1	0	918
x5	13	11	0	0	1	783
cj	2	4	0	0	0	0

  Таким образом, в данном базисном решении неосновные переменные 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 - старое значение разрешающего элемента.

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

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

Базис	Переменные					bi
	x1	x2	x3	x4	x5
x3	-8,182	0	1	0	-1,091	638,818
x4	2,091	0	0	1	-0,455	562,091
x2	1,182	1	0	0	0,091	71,182
cj	-2,727	0	0	0	-0,364	-284,727

   Таким образом, в новом базисном решении  базисными переменными являются: 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

2	7	1	2	5	18
8	2	9	5	9	18
1	17	4	6	3	18
7	9	21	5	7	18
14	14	14	16	14

Решение.

     Задача  имеет закрытый тип, т.к. запасы груза  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. 
 
 
 
 
 
 
 
 
 

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

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	2 0	7 0	1 14	2 4	5 0	18
A2	8 0	2 14	9 0	5 4	9 0	18
A3	1 14	17 0	4 0	6 0	3 4	18
A4	7 0	9 0	21 0	5 8	7 10	18
Потребность	14	14	14	16	14