Экономмико-математические методы и модели

Из  таблицы 4   видно, что значение линейной формы возросло и теперь равно 6. Однако наличие в индексной строке отрицательных чисел свидетельствует о том, что это значение еще модно увеличить. Переходим к следующей симплексной таблице. Число «0,4» определяет ведущий столбец. А, как видно из последнего столбца минимальных симплексных отношений, число 6 определяет ведущую строку. Итак, разрешающим элементом  будет 2,2. Вектор А₁ вводим в базис вместо вектора А₃. пересчет коэффициентов осуществляем по указанным выше правилам и получаем таблицу.

                                                                                                                                  Таблица  5.       

     В индексной строке нет отрицательны элементов. Следовательно, мы получили оптимальную программу. Оптимальное  решение:

     х₁= 3.8,  х₂= 3,4,  у₁= 9,5,  у₂=0,  у₃ =0.

б) Теперь с помощью симплексных  таблиц найдем решение целевой функции на оптимизацию суммарного выпуска:   f = х₁ + х₂       max

     х₁ 0, х₂ 0

     Линейная  форма имеет вид:

     f = 1х₁ + 1х₂ + 0y₁ + 0y₂ + 0y₃.

     Векторы А_3,  А_4,  А₅ образуют базис. Это означает, что, присвоив х₁ = 0, х₂ = 0, получаем первое базисное решение: х₁=0; х₂=0; у₁=27; у₂=2; у₃ =42.

     При этом линейной формы f = 0. На этом основании строим первую симплексную таблицу.

                                                                                                                                   Таблица  6.                    

     Так как в индексной строке присутствуют отрицательные числа, то используя  вышеописанный алгоритм, переходим  к следующей симплексной таблице. Ведущий столбец будет  А₁, минимальное симплексное отношение определяет ведущую строку и в данном случае ведущая строка будет первой.  Разрешающий элемент будет 4.                                                                                                                                           

                                                                                                                          Таблица 7.       

     В  таблице 7 тоже есть отрицательные числа в индексной строке, это означает, что мы ещё не получили оптимальное решение в данной таблице. Поэтому переходим  к следующей симплекс таблице.                                                                                                                               

                                                                                                                   Таблица 8.    

     В индексной строке нет отрицательны элементов. Следовательно, мы получили оптимальную программу. Оптимальное  решение:

     х₁= 6,  х₂= 1,  у₁= 7,  у₂=0,  у₃ =0.

2.4. Основные способы решения транспортной задачи

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

     В 4 пунктах отправления  А_1, А_{2 ,} А_3, А₄ (поставщики) сосредоточено определенное количество единиц некоторого продукта, которое обозначим а_i (i=1,2,3,4). Данный продукт потребляется в 5 пунктах В₁, В₂, В₃, В₄, В₅ (потребители); объем потребления обозначим b_j (j=1, 2, 3, 4, 5). Будем считать, что общее количество продукции у всех поставщиков равно суммарной потребности в ней. Известны расходы на перевозку единицы продукта из пункта А_i в пункт В_j, которые равны с_ij и приведены в матрице транспортных расходов С= (с_ij).