Суммарные запасы и суммарные потребности не совпадают

Страницы работы

11 страниц (Word-файл)

Содержание работы

Задание 2

Имеется четыре карьера, производящих строительные материалы, и четыре потребителя сырья строительных материалов. Известны объемы производства на каждом карьере, потребности в их продукции каждого из потребителей, а также стоимость перевозки одной тонны продукции I-го карьера а J-му потребителю. Определить При какие объемах грузоперевозок от I-го поставщика к J-му потребителю суммарная стоимость перевозок будет минимальной.

1.  Решить задачу посредствам Excel (Надстройка «Поиск решения»).

2.  Решить задачу аналитически.

Вариант 4

Таблица 1

Поставщик

Потребители

Запасы

1

2

3

4

1

2

4

6

8

120

2

2

2

3

5

140

3

3

1

4

3

230

4

1

5

6

4

200

Потребности

150

120

300

160

Решение.

1. Решение методом потенциалов

Построим математическую модель данной задачи

Вычислим суммарные запасы:

 


и суммарные потребности:

 


Суммарные запасы и суммарные потребности не совпадают => это задача открытого типа.

Данная задача решается введением фиктивного поставщика.

Стоимость всех фиктивных перевозок равна нулю.

Построим опорное решение методом «северо-западного» угла (таблица 2)

Таблица 2

Суммарная стоимость перевозок равна:

 


Рассчитаем систему потенциалов для этого решения.

Для определения U1, U2, U3, U4, V1, V2, V3, V4 имеем следующую систему уравнений:

                        Имеем 8 уравнений и 9 неизвестных.

Положим что U1=0, тогда остальные величины будут равны:

V1=2,

V2=2

V3=5

V4=3

U2=0

U3=1

U4=-1

U5=3

Припишем значения потенциалов соответствующим строкам и столбцам (таблица 3).

Введем дополнительный столбец Ui и дополнительную строку Vj и занесем вычисленные значения потенциалов в полученные клетки

Таблица 3

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

 


В ряде клеток (2,3) и (4,1) наблюдаются нарушения  (невязка больше нуля)

Выберем клетку (2,3) в которой превышение равно 2.

Построим замкнутый цикл с началом в этой точке.

В качестве остальных вершин выберем клетки (3,3), (3,2), (2,2)

Нечетные вершины (2,3), (3,2) образуют положительную полуцепь.

Четные вершины (3,3), (2,2) образуют отрицательную полуцепь.

Величина q=min{110;220}=110

Вычислим новые значения для узлов контура. В четных вершинах значения уменьшаются на 110, в клетке (2,2) значение станет равным 110-q=0

в клетке (3,3) - равным 220-q=220-110=110

В нечетных вершинах значение увеличивается на q=110, так в клетке (2,3) значение равно 0+q=0+110=110

а в клетке (3,2) значение равно 10+q=10+110=120

Получим новое опорное решение (таблица 4)

Таблица 4

Вычислим суммарную стоимость перевозок для полученного опорного плана:

 


Уменьшение стоимости перевозок по сравнению с начальным планом составило:

 


Теоретически это уменьшение равно

q - множитель на соответствующее превышение т.е. те же 220 (произведение 110 на 2)

Рассчитаем новую систему потенциалов.

Для определения U1, U2, U3, U4, V1, V2, V3, V4 имеем следующую систему уравнений:

                        Имеем 8 уравнений и 9 неизвестных.

Положим что U1=0, тогда остальные величины будут равны:

V1=2

V2=0

V3=3

V4=1

U2=0

U3=-1

U4=-3

U5=1

Припишем значения потенциалов соответствующим строкам и столбцам (таблица 5).

Таблица 5

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

 


В ряде клеток (4,1), (5,1) и (5,3) наблюдаются нарушения  (невязка больше нуля)

Выберем клетку (4,1) в которой превышение равно 4.

Построим замкнутый цикл с началом в этой точке.

В качестве остальных вершин выберем клетки (2,1), (2,3), (4,3)

Нечетные вершины (4,1), (2,3) образуют положительную полуцепь.

Четные вершины (2,1), (4,3) образуют отрицательную полуцепь.

Величина q=min{30;80}=30

Похожие материалы

Информация о работе