Характеристика входной и выходной информации

На четыре базы А1, А2, А3, А4 поступил однородный груз в количествах, соответственно равных 180, 160, 140 и 220 единиц. Этот груз требуется перевезти в четыре пункта назначения В1, В2, В3, В4 соответственно в количествах 150, 250, 120 и 180 единиц. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения показаны далее (Таблица 2):

Таблица 2 — Входные данные.

Выходной информацией является целевая функция равная 8040 единицам, указывающая, что определен оптимальный план перевозки груза (Таблица 3).

Таблица 3 — Выходные данные

Из получившихся результатов видим, что первый пункт отправления (А1) доставит 60 и 120 единиц груза соответственно в пункты назначения (В1 и B3). Второй пункт отправления (А2) доставит груз в пункты В1 и В4 в количестве 10, 150 соответственно. Третий пункт отправления (А3) доставит груз в пункты назначения В3 В количестве 140 единиц. Четвертый пункт отправления (А4) доставит груз в пункты В2 и В4 в количестве 190, 30 соответственно.

Математическое описание задачи

Имеются следующие исходные данные.

Наличие однородного груза на базах (см. таблицу 2.1).

Таблица 2.1 — Наличие груза.

Потребность в грузе на различных пунктах (см. таблицу 2.2).

Таблица 2.2 — Потребность в грузе.

Расстояния между складами и пунктами доставки (см. таблицу 2.3).

Таблица 2.3 — Расстояния между пунктами доставки.

Таблица 2.4 — опорное решение (метод мин. элемента).

Е = 2*30+3*120+12*30+3*150+7*10+12*140+1*220=3200 ден. ед.

Цикл 1.

Шаг 1. Составим систему уравнений для определения платежей по формуле: U_i+V_j=C_ij, где C_ij — это стоимость перевозок соответствующая Базисным переменным. U_i — платежи (потенциалы поставщиков), V_j — платежи (потенциалы потребителей).

Система уравнений платежей:

U1+V2=2.

U2+V3=3.

U1+V4=12.

U2+V1=3.

U2+V4=7.

U3+V4=12.

U4+V2=1.

Шаг 2. Из полученной системы определим платежи. Один из платежей (обычно U1) принимают равным нулю.

Пусть U1=0, тогда:

V2=2.

V3=3.

V1=8.

U2=-5.

V4=12.

U4=-1.

U3=0.

Шаг 3. Для всех не Базисных переменных находим суммы платежей (псевдостоимости):

Шаг 4. Для всех не Базисных переменных находим разности стоимости и псевдостоимости:

Шаг 5. Если для всех величин D_ij выполняется условие D_ij? 0 то оптимальное решение найдено. Если имеются D_ij? 0 то выполняется следующий шаг.

Шаг 6. Определяется переменная для включения в Базис. Для этого выбирается переменная, которая соответствует максимальному по модулю отрицательному элементу D_ij. В этой ячейке ставится знак «+» т. е. обязательно должны выполняться перевозки от i — поставщика к j — потребителю. Так как максимальный по модулю D₃₄= -5, то переменная х₃₄ включается в Базис.

Шаг 7. Определяется переменная для исключении из Базиса, для чего строится цикл. Минимальная из х_ij помеченных знаком «-» при построении цикла исключаются из Базиса и обозначаются х_rs. В нашем случае х_rs=х₁₄=30.

Шаг 8. Определим новый план перевозок. Все переменные помеченные знаком «+» увеличиваем на величину х_rs, а знаком «-» уменьшаем.

Таблица 2.5 — Оптимизированный план.

Е = 2*60+3*120+12*30+3*150+7*10+12*140+1*190+6*30=2870 ден.ед.

Цикл 2.

Шаг 1. Составим систему уравнений для определения платежей по формуле: U_i+V_j=C_ij, где C_ij — это стоимость перевозок соответствующая Базисным переменным. U_i — платежи (потенциалы поставщиков), V_j — платежи (потенциалы потребителей).

Система уравнений платежей:

U1+V2=2.

U1+V3=3.

U4+V4=6.

U2+V1=3.

U2+V4=7.

U3+V4=12.

U4+V2=1.

Шаг 2. Из полученной системы определим платежи. Один из платежей (обычно U1) принимают равным нулю.

Пусть U1=0, тогда:

V2=2.

V3=3.

V1=3.

U2=-0.

V4=7.

U4=-1.

U3=5.

Шаг 3. Для всех не Базисных переменных находим суммы платежей (псевдостоимости):

Шаг 4. Для всех не Базисных переменных находим разности стоимости и псевдостоимости:

Шаг 5. Если для всех величин D_ij выполняется условие D_ij? 0 то оптимальное решение найдено. Если имеются D_ij? 0 то выполняется следующий шаг.

Шаг 6. Определяется переменная для включения в Базис. Так как максимальный по модулю D₃₁= -4, то переменная х₃₁ включается в Базис.

Шаг 7. Определяется переменная для исключении из Базиса. В нашем случае х_rs=х₃₄=140.

Шаг 8. Определим новый план перевозок. Все переменные помеченные знаком «+» увеличиваем на величину х_rs, а знаком «-» уменьшаем.

Таблица 2.6 — Оптимизированный план.

Е = 2*30+3*120+12*30+3*10+7*150+4*140+1*190+6*30=2490 ден.ед.

Цикл 3.

Шаг 1. Составим систему уравнений для определения платежей по формуле:

U_i+V_j=C_ij,.

где C_ij — это стоимость перевозок соответствующая Базисным переменным. U_i — платежи (потенциалы поставщиков), V_j — платежи (потенциалы потребителей).

Система уравнений платежей:

U1+V2=2.

U1+V3=3.

U2+V1=3.

U2+V4=7.

U3+V1=4.

U4+V2=1.

U4+V4=6.

Шаг 2. Из полученной системы определим платежи. Один из платежей (обычно U1) принимают равным нулю.

Пусть U1=0, тогда:

V3=3.

V4=7.

V1=2.

V2=2.

U2=0.

U4=-1.

U3=1.

Шаг 3. Для всех не Базисных переменных находим суммы платежей (псевдостоимости):

Шаг 4. Для всех не Базисных переменных находим разности стоимости и псевдостоимости:

Шаг 5. Так как для всех величин D_ij выполняется условие D_ij? 0 то оптимальное решение найдено.