Составим экономико-математическую модель задачи

Обозначим— объемы продуктов (кг) в рационе. Тогда необходимо определить вектор Составим экономико-математическую модель задачи - student2.ru , удовлетворяющий следующим условиям:

Составим экономико-математическую модель задачи - student2.ru (2.6.1)

и обеспечивающий минимум целевой функции:

Составим экономико-математическую модель задачи - student2.ru (2.6.2).

Решение.Приведем систему ограничений (6.1) к системе неравенств смысла « Составим экономико-математическую модель задачи - student2.ru », умножив обе части неравенств на (—1).

Составим экономико-математическую модель задачи - student2.ru .

Переходим к системе уравнений:

Составим экономико-математическую модель задачи - student2.ru

За базис выбираем систему векторов Составим экономико-математическую модель задачи - student2.ru ,так как эти векторы единичные и линейно независимые. Соответствующие единичным векторам переменные Составим экономико-математическую модель задачи - student2.ru являются базисными. Полагая, что свободные переменные Составим экономико-математическую модель задачи - student2.ru = Составим экономико-математическую модель задачи - student2.ru = Составим экономико-математическую модель задачи - student2.ru =0, получим первый опорный план, который заносим в симплексную таблицу 2.6.2.

Составим экономико-математическую модель задачи - student2.ru =(0, 0, 0, -60, -50, -12), F( Составим экономико-математическую модель задачи - student2.ru )=0.

План I в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. Среди отрицательных значений базисных переменных выбираем наибольшее по абсолютной величине значение: |-60|>|-50|, |-12|. Следовательно, строка 1 симплексной таблицы является ведущей, а переменную Составим экономико-математическую модель задачи - student2.ru следует вывести из базиса. В строку Составим экономико-математическую модель задачи - student2.ru заносим следующие величины:

Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru .

Минимальное значение 9 соответствует 3-му столбцу, т.е. переменную Составим экономико-математическую модель задачи - student2.ru необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный —4.

Далее выполняем преобразование симплексной таблицы методом Жордана — Гаусса и заполняем план II.

Третий опорный план является оптимальным, так как в индексной строке все коэффициенты Составим экономико-математическую модель задачи - student2.ru 0, то условие оптимальности выполняется, а все значения базисных переменных — положительные числа:

Составим экономико-математическую модель задачи - student2.ru =(0; 8; 9; 0; 0; 47), F( Составим экономико-математическую модель задачи - student2.ru )=186.

Таблица 2.6.2

План Базисная переменная Значения базисной переменной Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru
I Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru -60 -1 -3 -4
Составим экономико-математическую модель задачи - student2.ru -50 -2 -4 -2
Составим экономико-математическую модель задачи - student2.ru -12 -1 -4 -3
  Составим экономико-математическую модель задачи - student2.ru -9 -12 -10
  Составим экономико-математическую модель задачи - student2.ru - 2.5 - - -
II Составим экономико-математическую модель задачи - student2.ru 0.25 0.75 -0.25
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru -20 -1.5 -2.5 -0.5
Составим экономико-математическую модель задачи - student2.ru -0.25 -1.75 -0.75
  Составим экономико-математическую модель задачи - student2.ru -6.5 Составим экономико-математическую модель задачи - student2.ru -4.5 -2.5
  Составим экономико-математическую модель задачи - student2.ru - 13/3 1.8 - - -
III Составим экономико-математическую модель задачи - student2.ru -0.7 -0.4 0.3
Составим экономико-математическую модель задачи - student2.ru 0.6 0.2 -0.4
Составим экономико-математическую модель задачи - student2.ru 0.8 -0.4 -0.7
  Составим экономико-математическую модель задачи - student2.ru -3.8 -1.6 -1.8

Пример 2.Содержание и постановка задачи анализа коммерческой деятельности предприятия изложены в п. 2.2.1, затем в разделе п. 2.4.1 (пример 2) проведено решение геометрическим методом, а теперь решим ее двойственным симплексным методом,

поскольку ограничения в модели задачи представлены в двух вариантах: Составим экономико-математическую модель задачи - student2.ru и Составим экономико-математическую модель задачи - student2.ru .

Решение.Приведем систему ограничений задачи к системе неравенств вида Составим экономико-математическую модель задачи - student2.ru :

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru .

Затем переходим к системе уравнений введением дополнительных переменных:

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru .

Полагая, что свободные переменные Составим экономико-математическую модель задачи - student2.ru , получим первый опорный план, который запишем в симплексную таблицу 2.6.3, причем

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =(0; 0; 3; 4; 1,5; 2; -0,25; -0,5).

Поскольку в индексной строке коэффициенты Составим экономико-математическую модель задачи - student2.ru , а среди значений столбца свободных членов имеются отрицательные числа, то план является не оптимальным, или псевдопланом.

Затем определяем ведущую строку по максимальной абсолютной величине отрицательных чисел столбца свободных членов: |-0,5| >|-0,25|, следовательно, Составим экономико-математическую модель задачи - student2.ru выводим из базиса.

Для определения ведущего столбца коэффициенты индексной строки делим на соответствующие только отрицательные коэффициенты ведущей строки, результаты деления заносим в строку Составим экономико-математическую модель задачи - student2.ru , из которой выбираем минимальный 2, что соответствует переменной Составим экономико-математическую модель задачи - student2.ru , которую следует ввести в базис вместо Составим экономико-математическую модель задачи - student2.ru . На пересечении ведущих строки и столбца находится разрешающий элемент (—1). Далее выполняем преобразование симплексной таблицы методом Жордана - Гаусса и заполним план II таблицы 2.6.3.

Третий план является оптимальным, поскольку все значения базисных переменных есть положительные числа, и в индексной строке условие оптимальности выполняется:

Составим экономико-математическую модель задачи - student2.ru =(0,5; 0,25; 2,375; 3,125; 2; 1,75; 0; 0) , Составим экономико-математическую модель задачи - student2.ru =1,75.

Такой же ответ получен в решении этой задачи в примере 2 раздела 2.4.1 геометрическим методом.

Таблица 2.6.3

План Базисная переменная Значения базисной переменной Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru
I Составим экономико-математическую модель задачи - student2.ru 0.5 +1
Составим экономико-математическую модель задачи - student2.ru 0.5 +1
Составим экономико-математическую модель задачи - student2.ru 1.5 -1 +1 1.5
Составим экономико-математическую модель задачи - student2.ru +1
Составим экономико-математическую модель задачи - student2.ru -0.25 -1 +1 0.25
Составим экономико-математическую модель задачи - student2.ru -0.5 -1 +1 -
  Составим экономико-математическую модель задачи - student2.ru -2 -3  
  Составим экономико-математическую модель задачи - student2.ru   - - - - - - -  
II Составим экономико-математическую модель задачи - student2.ru 2,75 1,5 +1  
Составим экономико-математическую модель задачи - student2.ru 3,5 1,5 +1  
Составим экономико-математическую модель задачи - student2.ru +1 -1  
Составим экономико-математическую модель задачи - student2.ru +1  
Составим экономико-математическую модель задачи - student2.ru -0,25 -1 +1  
Составим экономико-математическую модель задачи - student2.ru 0,5 -1  
  Составим экономико-математическую модель задачи - student2.ru -3 -2  
  Составим экономико-математическую модель задачи - student2.ru   - +3 - - - - -  
III Составим экономико-математическую модель задачи - student2.ru 2,375 +1 1,5  
Составим экономико-математическую модель задачи - student2.ru 3,125 +1 1,5  
Составим экономико-математическую модель задачи - student2.ru +1 -1  
Составим экономико-математическую модель задачи - student2.ru 1,75 +1  
Составим экономико-математическую модель задачи - student2.ru 0,25 -1  
Составим экономико-математическую модель задачи - student2.ru 0,5 -1  
  Составим экономико-математическую модель задачи - student2.ru 1,75 -3 -2  

Контрольные вопросы

1. Какие задачи линейного программирования решаются двойственным симплексным методом?

2. В чем отличие симплексного метода и двойственного симплексного метода?

3. Как осуществляется переход от одного псевдоплана к другому?

4. В чем состоит критерий оптимальности двойственного симплексного метода?

Задачи

Решить задачи 1-10 двойственным симплексным методом.

1. Составим экономико-математическую модель задачи - student2.ru 2. Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru ;

3. Составим экономико-математическую модель задачи - student2.ru 4. Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru ;

5. Составим экономико-математическую модель задачи - student2.ru 6. Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru ;

7. Составим экономико-математическую модель задачи - student2.ru 8. Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru ;

9. Составим экономико-математическую модель задачи - student2.ru 10. Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru ; Составим экономико-математическую модель задачи - student2.ru .

Метод потенциалов

В п. 2.2.5 сформулирована задача по перевозке грузов, которая называется транспортной задачей и заключается в определении оптимального плана перевозок некоторого однородного груза из mпунктов отправления Составим экономико-математическую модель задачи - student2.ru в nпунктов потребления Составим экономико-математическую модель задачи - student2.ru .

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

Экономико-математическая модель транспортной задачи (п. 2.2.5) содержит системы линейных уравнений (2.2.1) и (2.2.2), условие неотрицательности переменных Составим экономико-математическую модель задачи - student2.ru (2.2.3) и целевую функцию (2.2.4).

Следует иметь в виду, что:

1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей Составим экономико-математическую модель задачи - student2.ru ; называется допустимым планомтранспортной задачи.

2. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т.е. равен (m+n-1). Следовательно, число линейно независимых уравнений равно (m+n-1), они образуют базис, а соответствующие им (m+n-1) переменные будут являться базисными.

3. Допустимый план транспортной задачи, имеющий не более (m+n-1) отличных от нуля величин Составим экономико-математическую модель задачи - student2.ru , называется опорным.

4. Если в опорном плане число отличных от нуля компонент равно в точности (m+n-1), то план является невырожденным, если меньше, то план называется вырожденным.

5. План Составим экономико-математическую модель задачи - student2.ru , при котором функция (2.2.4) принимает свое минимальное значение, называется оптимальным планомтранспортной задачи.

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

Составим экономико-математическую модель задачи - student2.ru .(2.7.1)

7. Модель транспортной задачи, удовлетворяющая условию (7.1), называется закрытой.Если же указанное условие не выполняется, то модель называется открытой.

Вслучае превышения запаса над заявками

Составим экономико-математическую модель задачи - student2.ru

вводится фиктивный (n+1)пункт назначения с потребностью Составим экономико-математическую модель задачи - student2.ru , соответствующие тарифы считаются равными нулю: Составим экономико-математическую модель задачи - student2.ru .

При Составим экономико-математическую модель задачи - student2.ru вводится фиктивный (m+1) пункт отправления с запасом груза Составим экономико-математическую модель задачи - student2.ru и соответствующие тарифы принимаются равными нулю: Составим экономико-математическую модель задачи - student2.ru .

8. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф — если задача поставлена на максимум целевой функции.

Рассмотрим один из методов построения первого опорного плана — метод наименьших тарифов(стоимости).

Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы:

а) среди тарифов находится наименьший;

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

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

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

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

9. Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов,который основан на теории двойственности.

План Составим экономико-математическую модель задачи - student2.ru транспортной задачи будет являться оптимальным,

если существует система m+nчисел Составим экономико-математическую модель задачи - student2.ru , называемых потенциалами, удовлетворяющая условиям:

I) Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru (2.7.2)

II) Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru (2.7.3)

где 1-е уравнение в системах для занятых клеток, 2-е - для незанятых клеток.

Потенциалы Составим экономико-математическую модель задачи - student2.ru являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу Составим экономико-математическую модель задачи - student2.ru , а условия (2.7.2), (2.7.3) получены на основании второй теоремы двойственности.

Введем обозначение оценки свободной клетки таблицы

Составим экономико-математическую модель задачи - student2.ru .

Если среди оценок Составим экономико-математическую модель задачи - student2.ru нет положительных (задача поставлена на минимум), то опорный план является оптимальным.

Алгоритм оценки оптимальности плана методом потенциаловвключает следующие этапы.

а. Построение первого опорного плана.

б. Проверка вырожденности плана. Потенциалы Составим экономико-математическую модель задачи - student2.ru могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем

(m+n-1), то не хватит количества уравнений для определения потенциалов, поэтому

вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n-1). Нуль вводят в клетку с наименьшим тарифом, например в клетку одновременно вычеркиваемых строки и столбца таблицы при составлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы.

в. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы.

г. Проверка условия оптимальности. Определяем потенциалы Составим экономико-математическую модель задачи - student2.ru . Для каждой занятой клетки таблицы записываем уравнение Составим экономико-математическую модель задачи - student2.ru . Получим систему (m+n-1)

уравнений с (m+n) переменными.

Так как число переменных больше числа уравнений (m+n > m+n-1), то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов Составим экономико-математическую модель задачи - student2.ru задают произвольное значение, например для простоты вычислений полагаем Составим экономико-математическую модель задачи - student2.ru =0. Тогда остальные потенциалы определяются из приведенных соотношений. В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы.

Определяем оценки свободных клеток Составим экономико-математическую модель задачи - student2.ru .

Если все Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru (задача решается на минимум целевой функции) либо все Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки Составим экономико-математическую модель задачи - student2.ru >0 (задача поставлена на минимум) или Составим экономико-математическую модель задачи - student2.ru <0

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

д. Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных — наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых и связанных с заполняемой так называемым циклом.

Циклом, или прямоугольным контуром,в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья – вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое — в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл.

Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «—».

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его Составим экономико-математическую модель задачи - student2.ru . Перераспределяем величину j по циклу, прибавляя Составим экономико-математическую модель задачи - student2.ru к соответствующим объемам груза, стоящим в плюсовых клетках, и вычитая Составим экономико-математическую модель задачи - student2.ru из объемов груза, находящихся в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной.

Полученный новый опорный план проверяется на оптимальность, т.е. возвращаемся к четвертому этапу алгоритма.

Примечания,

1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения Составим экономико-математическую модель задачи - student2.ru , то при перераспределении объемов груза освобождаются две (или несколько) клеток и план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наименьшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (m+n-1).

2. Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю ( Составим экономико-математическую модель задачи - student2.ru =0), то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

Составим экономико-математическую модель задачи - student2.ru (задача поставлена на минимум);

Составим экономико-математическую модель задачи - student2.ru (задача поставлена на максимум),

где Составим экономико-математическую модель задачи - student2.ru — величина перемещаемого по циклу объема груза;

Составим экономико-математическую модель задачи - student2.ru - оценка свободной клетки, в которую направляется груз при переходе к новому плану;

Составим экономико-математическую модель задачи - student2.ru - значение целевой функции на к-йитерации;

Составим экономико-математическую модель задачи - student2.ru - значение целевой функции на предыдущей итерации.

Пример 1.На три базы Составим экономико-математическую модель задачи - student2.ru поступил однородный груз в количествах, соответственно равных 6, 8, 10 ед. Этот груз требуется перевезти в четыре магазина Составим экономико-математическую модель задачи - student2.ru соответственно в количествах 4, 6, 8, 8 ед. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов (тыс. руб. за единицу груза):

Составим экономико-математическую модель задачи - student2.ru , Составим экономико-математическую модель задачи - student2.ru .

Надо составить план перевозок однородного груза с минимальными транспортными издержками.

Проверим необходимое и достаточное условие разрешимости задачи.

Составим экономико-математическую модель задачи - student2.ru

Составим экономико-математическую модель задачи - student2.ru

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой.

Чтобы получить закрытуюмодель, введем дополнительную (фиктивную) базу Составим экономико-математическую модель задачи - student2.ru с запасом груза, равным 2 ед. (26-24). Тарифы перевозки единицы груза из базы Составим экономико-математическую модель задачи - student2.ru во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу 2.7.1.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Среди тарифов из всей таблицы наименьшим является Составим экономико-математическую модель задачи - student2.ru =1, поэтому в клетку Составим экономико-математическую модель задачи - student2.ru направляем максимально возможный груз. Он равен min{6, 4}=4. Тогда Составим экономико-математическую модель задачи - student2.ru =4 и из базы Составим экономико-математическую модель задачи - student2.ru не вывезен груз в размере 2 ед., а потребность магазина Составим экономико-математическую модель задачи - student2.ru удовлетворена полностью.

Столбец таблицы Составим экономико-математическую модель задачи - student2.ru выходит из рассмотрения. Из оставшихся тарифов строки наименьший - Составим экономико-математическую модель задачи - student2.ru =2. В клетку Составим экономико-математическую модель задачи - student2.ru направляем максимально возможный груз, равный min{2, 6}=2. Тогда строка Составим экономико-математическую модель задачи - student2.ru выходит из рассмотрения, поскольку из базы Составим экономико-математическую модель задачи - student2.ru вывезен весь груз, а потребность второго магазина не удовлетворена на 4 ед. Из оставшихся тарифов наилучший Составим экономико-математическую модель задачи - student2.ru =3 и Составим экономико-математическую модель задачи - student2.ru =3. В клетку Составим экономико-математическую модель задачи - student2.ru направляем груз, равный min{8, 4}=4. При этом вычеркивается столбец Составим экономико-математическую модель задачи - student2.ru из рассмотрения. Из оставшихся тарифов наименьший Составим экономико-математическую модель задачи - student2.ru =3. В клетку Составим экономико-математическую модель задачи - student2.ru направляем груз, равный min{10, 8}=8. При этом потребность четвертого магазина удовлетворена, а из третьей базы не вывезены 2 ед. Этот нераспределенный груз направляем в клетку Составим экономико-математическую модель задачи - student2.ru , Составим экономико-математическую модель задачи - student2.ru =2. Потребность третьего магазина не удовлетворена на 2 ед. Направим от фиктивного поставщика — базы Составим экономико-математическую модель задачи - student2.ru — 2 ед. в клетку Составим экономико-математическую модель задачи - student2.ru , т.е. Составим экономико-математическую модель задачи - student2.ru =2.

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

Таблица 2.7.1

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Запасы Составим экономико-математическую модель задачи - student2.ru
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =1 Составим экономико-математическую модель задачи - student2.ru =2 Составим экономико-математическую модель задачи - student2.ru =7 Составим экономико-математическую модель задачи - student2.ru =4
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =0 Составим экономико-математическую модель задачи - student2.ru 2 - +  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =1 4 + 4 -  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =-1    
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =-7      
Потребности Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru
                 

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m+n-1=4+4-1=7. Следовательно, опорный план является невырожденным.

3.Определяем значение целевой функции первого опорного плана.

Составим экономико-математическую модель задачи - student2.ru =4*1+2*2+ 4*3 + 4*8 + 2*6 + 8*3 + 2*0=88 тыс. руб.

4. Проверим оптимальность опорного плана. Найдем потенциалы Составим экономико-математическую модель задачи - student2.ru по занятым клеткам таблицы, в которых Составим экономико-математическую модель задачи - student2.ru , полагая, что Составим экономико-математическую модель задачи - student2.ru =0 , решим систему уравнений:

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru

Занесем найденные значения потенциалов в таблицу 2.7.1 и вычислим оценки свободныхклеток Составим экономико-математическую модель задачи - student2.ru :

Составим экономико-математическую модель задачи - student2.ru =7+0-4=3; Составим экономико-математическую модель задачи - student2.ru =4+0-3=1; Составим экономико-математическую модель задачи - student2.ru =1+1-4=-2;

Составим экономико-математическую модель задачи - student2.ru =4+1-5=0; Составим экономико-математическую модель задачи - student2.ru =1+(-1)-2=-2; Составим экономико-математическую модель задачи - student2.ru = 2+(-1)-7=-6;

Составим экономико-математическую модель задачи - student2.ru =1+(-7)-0=-6; Составим экономико-математическую модель задачи - student2.ru =2+(-7)-0=-5; Составим экономико-математическую модель задачи - student2.ru =4+(-7)-0=-3.

Первый опорный план не является оптимальным, так как Составим экономико-математическую модель задачи - student2.ru >0 и Составим экономико-математическую модель задачи - student2.ru >0, поэтому переходим к его улучшению.

5. Выбираем максимальную оценку свободной клетки — Составим экономико-математическую модель задачи - student2.ru =3. Для клетки Составим экономико-математическую модель задачи - student2.ru построим цикл перераспределения груза. Для этого в перспективную клетку Составим экономико-математическую модель задачи - student2.ru поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «—»,

«+», «—». Цикл приведен в таблице 2.7.1.

Из грузов Составим экономико-математическую модель задачи - student2.ru , стоящих в минусовых клетках, выбираем наименьшее, т.е.

Составим экономико-математическую модель задачи - student2.ru =min{2, 4}=2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Составим экономико-математическую модель задачи - student2.ru , стоящих в минусовых клетках. В результате получим новый опорный план II, приведенный в таблице 2.7.2.

6. Определяем значение целевой функции:

Составим экономико-математическую модель задачи - student2.ru =88-2*3=82(тыс. руб.)

Таблица 2.7.2

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Запасы Составим экономико-математическую модель задачи - student2.ru
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =1 Составим экономико-математическую модель задачи - student2.ru =-1 Составим экономико-математическую модель задачи - student2.ru =4 Составим экономико-математическую модель задачи - student2.ru =1
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =0 Составим экономико-математическую модель задачи - student2.ru 4 -   2 +  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =4  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =2 +   2 -
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =-4      
Потребности Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru
                 

7. Количество занятых клеток в плане II — 7, следовательно, план невырожденный.

8. Проверяем оптимальность плана методом потенциалов, для этого находим потенциалы Составим экономико-математическую модель задачи - student2.ru по занятым клеткам, где Составим экономико-математическую модель задачи - student2.ru полагая, что Составим экономико-математическую модель задачи - student2.ru =0;

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru

Затем рассчитываем оценки свободных клеток:

Составим экономико-математическую модель задачи - student2.ru =0+(-1)-2=-3 ; Составим экономико-математическую модель задачи - student2.ru =0+1-3=-2 ; Составим экономико-математическую модель задачи - student2.ru =4+1-4=1;

Составим экономико-математическую модель задачи - student2.ru =4+1-5=0; Составим экономико-математическую модель задачи - student2.ru =2+1-2=1; Составим экономико-математическую модель задачи - student2.ru =2-1-7=-6;

Составим экономико-математическую модель задачи - student2.ru =-4+1-0=-3; Составим экономико-математическую модель задачи - student2.ru =-4-1-0=-5; Составим экономико-математическую модель задачи - student2.ru =-4+1-0=-3.

План, полученный в таблице 2.7.2, не оптимальный, так как Составим экономико-математическую модель задачи - student2.ru >0 и Составим экономико-математическую модель задачи - student2.ru >0.

9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем Составим экономико-математическую модель задачи - student2.ru , в которую записываем +, затем строим цикл перераспределения, приведенный в таблице 2.7.2.

В построенном цикле определяем величину Составим экономико-математическую модель задачи - student2.ru =min(4, 2)=2.

Перераспределив груз, получаем новый план III, приведенный в таблице 2.7.3.

Таблица 2.7.3

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Запасы Составим экономико-математическую модель задачи - student2.ru
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =1 Составим экономико-математическую модель задачи - student2.ru =-1 Составим экономико-математическую модель задачи - student2.ru =4 Составим экономико-математическую модель задачи - student2.ru =2
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =0 Составим экономико-математическую модель задачи - student2.ru 2 -   4 +  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =4 + 4 2 -  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =2 2  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =-4      
Потребности Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru
                 

10. Количество занятых клеток 7, а должно быть m+n-1=7, следовательно, план III невырожденный.

11. Вычислим значение целевой функции:

Составим экономико-математическую модель задачи - student2.ru =82-2-1=80 тыс. руб.

12. Проверяем оптимальность плана III методом потенциалов. Находим потенциалы по занятым клеткам:

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru

Рассчитываем оценки свободных клеток:

Составим экономико-математическую модель задачи - student2.ru =-1+0-2=-3; Составим экономико-математическую модель задачи - student2.ru =2+0-3=-1; Составим экономико-математическую модель задачи - student2.ru =1+4-4=1;

Составим экономико-математическую модель задачи - student2.ru =2+4-5=1; Составим экономико-математическую модель задачи - student2.ru =-1+1-7=-7; Составим экономико-математическую модель задачи - student2.ru =4+1-6=-1;

Составим экономико-математическую модель задачи - student2.ru =1+(-4)-0=-3; Составим экономико-математическую модель задачи - student2.ru =-1+(-4)-0=-5; Составим экономико-математическую модель задачи - student2.ru =2+(-4)-0=-2.

План не оптимальный, так как Составим экономико-математическую модель задачи - student2.ru >0 и Составим экономико-математическую модель задачи - student2.ru >0.

13. Проводим улучшение плана III перераспределения груза. В качестве перспективной клетки для загрузки выбираем Составим экономико-математическую модель задачи - student2.ru , которую записываем +, затем строим цикл перераспределения в таблице 2.7.3.

Определяем величину Составим экономико-математическую модель задачи - student2.ru =min{2;2}=2. После проведения операции перераспределения получаем план IV, приведенный в таблице 2.7.4.

14. План получается вырожденный, поскольку в минусовых клетках цикла находятся два одинаковых минимальных объема груза, равные 2, и при перераспределении две клетки Составим экономико-математическую модель задачи - student2.ru и Составим экономико-математическую модель задачи - student2.ru оказались свободными, поэтому число занятых клеток будет меньше, чем

m+n-1=7. Для продолжения решения в одну из освободившихся клеток — в клетку Составим экономико-математическую модель задачи - student2.ru , так как тариф Составим экономико-математическую модель задачи - student2.ru меньше Составим экономико-математическую модель задачи - student2.ru , записываем нуль.

15. Вычисляем значение целевой функции:

Составим экономико-математическую модель задачи - student2.ru =80-2*1=78 тыс. руб.

Таблица 2.7.4

Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Запасы Составим экономико-математическую модель задачи - student2.ru
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =1 Составим экономико-математическую модель задачи - student2.ru =0 Составим экономико-математическую модель задачи - student2.ru =4 Составим экономико-математическую модель задачи - student2.ru =2
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =0   6  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =3  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =1 2  
Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru =-4      
Потребности Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru Составим экономико-математическую модель задачи - student2.ru
                 

16. Проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам:

Наши рекомендации