Решение ТЗ открытого типа

Решить задачу, заданную таблицей

Проверяем задачу на условие правильности баланса. Имеем

Задача открытая: она неразрешима в такой постановке. Вводим «фиктивного» потребителя с потребностью b ₅=10 и принимаем c_i ₅=0, i =1, 2, 3.

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

«Фиктивный» потребитель рассматривается в последнюю очередь.

1) Определим начальный план.

Минимальный тариф с _зз=1 в клетке (3, 3). Положим х _зз=min(30, 90)=30 и запишем поставку в 30 ед. в эту клетку. Столбец j =3 зачеркнем под номером 1.

Минимальные тарифы с ₁₂= с ₃₄=2. Положим х ₁₂=20, столбец j =2 зачеркнем под номером 2. Далее возьмем х ₃₄=60 и одновременно зачеркнем строку i =3 и столбец j =4 под номером 3.

Учитывая с ₁₁=3, запишем х ₁₁=20 и зачеркнем строку i =1 под номером 4.

Следующая поставка х ₂₁=20 очевидна, столбец j =1 зачеркнем под номером 5.

В последнюю очередь рассматриваем «фиктивного» потребителя, записывая х ₂₅=10.

План вырожденный, потому что на 3-м шаге зачеркнули две линии (строку и столбец). В одну из клеток запишем нуль, т.е. занимаем одну клетку либо в 3-й строке, либо в 4-м столбце так, чтобы она не составляла с другими занятыми клетками замкнутый цикл. Из нескольких возможностей выбираем х ₃₁=0, потому что на момент зачеркивания этих линий в столбце j =1 сохранилась потребность в 20 ед. Таким образом, получили нужное количество занятых клеток: т + п -1=7.

2) Определим потенциалы занятых клеток, исходя из начального условия α₁=0. Остальные потенциалы вычисляем в уме и занесем их в эту же таблицу.

Найдем оценки распределения для свободных клеток и запишем в центрах клеток. Среди оценок отрицательных нет.