Решение задачи вручную

 

Находим значение потенциалов:

U_i+V_j=C_i,j(i=1..m, j=1..n),

U₁ + V₁=5

U₁ + V₂=7

U₁ + V₃=6

U₂ + V₃=5

U₂  + V₄=0

U₃ + V₄=0

U₁ =0

U₂=-1

U₃=-1

V₁=5

V₂=7

V₃=6

V₄=1

Определяем значения оценок _ij=C_ij-U_i-V_j для всех свободных клеток:

=

= =2

= =0

3

=0

Строим оценочную матрицу:

=

В оценочно матрице есть отрицательный элементы и, следуя, критерию оптимальности решение не является оптимальным. Переходим к следующему решению. Для этого нужно перераспределить данные в матрице Х₀

 

Находим число пересчета по циклу =min , которое равно минимальному

числу перегрузки, где - числа в базисных клетках цикла со знаком минус.

 

Составляем новую матрицу, добавив в клетки отмеченные плюсом прибавляем, и отнимаем из значение из клеток отмеченные минусом. Получаем новое решение X

=

18*5+1*7+31*6+2*5+38*0+20*4=373

В оценочной матрице подчеркиваем элементы соответствующие базисным в новом решении. Строим цепочку выделения. Она строится от особо выделенного элемента (элемент ) по строкам, затем по столбцам. Каждый элемент, попавший в цепочку выделяет и строку, и столбец кроме выделенного элемента.

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

=

 

=

18*5+1*7+31*0+33*5+7*0+20*4=342

 

=

=min =1

=

=

Так как в оценочной матрице , нет отрицательных элементов матрица Х_3, становиться оптимальна.

18*5+32*0+1*6+33*5+6*0+20*4=341

 

 

 

2.4. Решение задач с помощью Excel

Таблица №4

Поставщики	Потребители			Запасы груза
А1	5	7	6	50
А2	6	6	5	40
А3	8	4	5	20
Потребность в грузе	18	21	33

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

Рассмотрим, как это можно сделать в среде электронных таблиц Microsoft Excel.

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

1. Введите в ячейки диапазона A6:D8 значения спроса

2. Введите в диапазон ячеек A9:D9 матрицу расходов.

3. Введите в ячейки диапазона E6:E8 запасы.

4. В ячейку E9 выводиться оптимальное решение

=СУММПРОИЗВ(A1:D3;A6:D8). Сделать это можно при помощи мастера функций выбрав в разделе. Математические функцию СУММПРОИЗВ и указав необходимый диапазон.

 

Далее выбираем команду сервис, Поиск решений и заполняем открывшееся диалоговое окно Поиск решений.

В диалоговом окне Параметры поиска решения установить флажок Линейная модель. После нажатия кнопки. Выполнить средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы.

Оптимальное решение транспортной задачи