Прикладная математика

    Запишем процесс решения задачи в виде симплексной таблицы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

В данной симплексной таблице обращенным базисом Q^-1, соответствующим оптимальному набору базисных неизвестных является матрица

                                                    Q^-1=

Проверим  выполнение соотношения

                                   H= Q^-1B,

где В=

По определению  произведением матрицы Q^-1 размером (3×3) на матрицу В размером (3×1) является матрица Н размером (3×1), где 

h₁₁=1*110+1*126+(-2)*114=8

h₂₁=0*110+1/3*126+0*114=42

h₃₁=0*110+(-2/3)*126+1*114=30, т.е.

Н= , что соответствует матрице Н в третьем столбце последней симплексной таблицы. Таким образом, соотношение H= Q^-1 B выполняется.

Графический способ решения

    Воспользуемся тем, что в оптимальной производственной программе х2=0 и х4=0. Предположим, что вторую и четвертую продукции  мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Решим задачу графически. Математическая модель задачи будет выглядеть следующим образом:

                                                  (22)

            z = 30x1+9x3→max                                (23)

                                                              (24)  →   

             x1 ≥ 0, x3 ≥ 0                                       (25) 

 

     Система линейных неравенств (24) и (25) определяет выпуклый многоугольник OPQRS допустимых решений. Линии уровня функции z перпендикулярны вектору-градиенту grad z = (30; 9) и образуют семейство параллельных прямых. Наибольшего значения функция z достигает в точке Q. Координаты этой точки определяют оптимальный план производства х1=42, х3=30, а максимальная прибыль будет равна 1530.

    Последовательное  улучшение производственной программы 

     (х1=0, х3=0)→(х1=42, х3=0)→(х1=42, х3=30)

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

    ДВОЙСТВЕННАЯ  ЗАДАЧА 

    Технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С  имеют вид:

          А=         В=        С=(30, 28, 9, 23)                            

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

                                                 (у1, у2, у3),

минимизирующий  общую оценку всех ресурсов

                                           f=110у1+126у2+114у3                        (1)

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

                                                                    ,                                   (2)

причем  оценки ресурсов не могут быть отрицательными

                       у1≥0, у2≥0, у3≥0.                                (3)

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

              (х1, х2, х3, х4) и (у1, у2, у3) пары двойственных задач необходимо и достаточно выполнение условий

                                                                        

    

    Ранее было найдено, что в решении исходной задачи х1>0, x3>0. Поэтому

                                         

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

                                      у1=0,

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

                                            

откуда  следует

                           у2=4, у3=9.

    Таким образом, получили двойственные оценки ресурсов

                       У1=0, у2=4, у3=9.

    Общая оценка всех ресурсов равна

                     f=110*0+126*4+114*9

                     f=1530.

ЗАДАЧА  О «РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА» 

    При выполнении оптимальной производственной программы второй и третий ресурсы  используются полностью, то есть образуют «узкие места производства». Будем  заказывать их дополнительно.

    T(t1, t2, t3) – вектор дополнительных объемов ресурсов.

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

                                 Н+Q^-1T ≥ 0.

    Необходимо  найти вектор T(0, t2, t3),

максимизирующий суммарный прирост прибыли

                                   W = 4t2 + 9t3                                                 (1)

При условии  сохранения двойственных оценок ресурсов и структуры производственной программы

                                                     (2)

    Мы  можем получить дополнительно не более 1/3 первоначального объема ресурса  каждого вида

                                                              (3),

    причем  t2 ≥ 0, t3 ≥ 0.                                                 (4)

    Перепишем неравенства (2) и (3) в виде:

                                                                                         (5)

                            t2 ≤ 126/3, t3 ≤ 114/3,

                            t2 ≤ 42, t3 ≤ 38.                                          (6)

    Приходим  к задаче линейного программирования:

    максимизировать W = 4t2 + 9t3 при условиях (4), (5), (6).

    Решим задачу графически: 
 
 
 
 
 
 
 
 
 
 
 
 

    Наибольшего значения функция W достигает в точке М(42, 25). Таким образом, программа расшивки имеет вид:

                                   t1 = 0, t2 = 42, t3 = 25

и прирост  прибыли составит

              W = 4*42+9*25

              W = 393.

Результаты  запишем в виде таблицы:

ТРАНСПОРТНАЯ  ЗАДАЧА ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ 

    Однородный  продукт, сосредоточенный в трех пунктах производства в количествах а1, а2, а3 единиц, необходимо распределить между четырьмя пунктами потребления, которым необходимо соответственно b1, b2, b3, b4 единиц. Стоимость перевозки единицы продукта  из i-го пункта отправления в j-й пункт назначения равна с_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были бы минимальными.

    Обозначим через х_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

                                                                            (1)

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

найти план перевозок 

                             Х= (х_ij)_,           i=1,2,3;          j=1,2,3,4,

минимизирующий  общую стоимость всех перевозок 

                                          L =                                  (2)

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

                                                  i=1,2,3                         (3)

и любому потребителю  доставляется необходимое количество груза

                                                  j=1,2,3,4                       (4)

по смыслу задачи

                            х₁₁ > 0,…, x_mn > 0.                                                        (5)

    Исходные  данные задачи имеют вид

    А(а1, а2, а3)=(65, 40, 70);    В(b1, b2, b3, b4)=(30, 58, 32, 43);  

    C=

    Общий объем производства ∑а_i =65+40+70=175 больше, чем требуется всем потребителям ∑b_j=30+58+32+43=163, то есть мы имеем открытую модель транспортной задачи. Решим задачу с помощью метода потенциалов. Для превращения задачи в закрытую модель вводим фиктивный пункт потребления с объемом потребления 175-163=12 единиц. Тарифы на перевозку в этот пункт условимся считать равными нулю.

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

      Транспортная таблица 1