Реферат: Анализ экономических задач симплексным методом

5.5 Задача о размещении заказа.

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

§7. Анализ задачи об оптимальном использовании сырья.

Исходя из специализации и своих технологических возможностей  предприятие может выступать четыре вида продукции. Сбыт любого количества обеспечен. Для изготовления этой продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объём ресурсов, расход каждого ресурса за единицу продукции, приведены в таблице 1. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить после оптимизационный анализ решения и параметров модели.

Решение.

Пусть - объёмы продукции планируемый к выпуску; - сумма ожидаемой выручки.

Математическая модель пря мой задачи:

Математическая модель двойственной задачи:

По условиям примера найти:

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

2.    Оценки ресурсов, используемых при производстве продукции.

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

После второй итерации все оценки оказались отрицательными, значит, найденный опорный план является оптимальным: , 

Основные переменные показывают, что продукциюи  выпускать нецелесообразно, а продукции  следует произвести 400 ед., - 500 ед. 

Дополнительные переменные и  показывают, что ресурсы используются полностью , а вот равенство  свидетельствует о том, что 200 единиц продукции  осталось неиспользованным.

Выпишем из таблицы2. Компоненты оптимального плана двойственной задачи – двойственные оценки. В канонической форме прямой задачи переменные  - являются свободными, а дополнительные переменные - базисными. В канонической форме двойственной задачи свободными будут переменные - а базисными

Соответствие между переменными примет вид

Учитывая это соответствие, выпишем из индексной строки последней итерации компоненты искомого плана  - двойственные оценки.

min f = max Z =84000.

Запишем это неравенство в развернутой форме:

48000*15 + 2400*5 + 1500*0 = 65*0 + 70*0 + 60*400 + 120*500

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

При оптимальном плане оценка ресурсов, затраченных на выпуск продукции, совпадает с оценкой произведенной продукции.  

Теперь  установим степень дефицитно­сти используемых ресурсов и обоснуем рентабельность оптимального плана.

Мы нашли оптимальный план выпуска продукции. При этом плане третье ограничение прямой задачи выполняется как строгое неравенство:

0+2-400+500= 1300< 1500. Это означает, что расход ресурса  мень­ше его запаса, т. е. ресурс  избыточный. Именно поэтому в оптималь­ном плане  двойственной задачи оценка  этого ресурса равна нулю.

А вот оценки  и  ресурсов  и  выражаются положительными числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при оптимальном плане используются полностью. В самом деле, ограни­чения по этим ресурсам выполняются как строгие равен­ства: 4.0+2.0+2.400+8.500=4800, 2-0+10.0+6.400=2400.

Поскольку 15>5, ресурс  считается более дефицитным, чем ресурс .

На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не вошла в опти­мальный план продукция и : первое и второе ограничения двой­ственной задачи выполняются как строгие неравенства: 4-15+2-5+0>65, 2-15+10*5>70.

Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции  и , превышают оценки единицы этой продукции. Понятно, что такую продукцию выпу­скать предприятию невыгодно. Что же касается продукции  и  , то выпуск ее оправдан, поскольку оценка израсходо­ванных ресурсов совпадает с оценкой произведенной продукции: 2*15+ +6*5+2*0=60, 8*15+0=120.

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

Рассмотрим возможность дальней­шего совершенствования оптимального ассортимента выпускаемой про­дукции.

Выше установлено, что ресурсы  и  являются дефицитными. В связи с этим на основе теоремы (об оценках) можно утверждать, что на каждую единицу ресурса , введенную дополнительно в производ­ство, будет получена дополнительная выручка , численно равная . В самом деле, при получаем . По тем же причинам каждая дополнительная единица ресурсаобеспечит прирост  выручки, равный 5 р. Теперь становится понятно, почему ресурс считается более дефицитным по сравнению с ресурсом : он может содействовать получению большей выручки.

Что же касается избыточного ресурса , то увеличение его запаса не приведет к росту выручки, поскольку . Из приве­денных рассуждений следует, что оценки ресурсов позволяют совершен­ствовать план выпуска продукции.

Выясним экономический смысл оценок продукции ,,,.

По оптимальному плану выпускать следует продукцию и . Оценки  и  этих видов продукции равны нулю. Что это означает, практически станет ясно, если представить оцен­ки в развернутой записи:

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

Что же касается продукции  и  являющейся, как установлено выше, убыточной, а потому и не вошедшей в оптимальный план, то для ее оценок  и получаем:

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

§8. Программа и расчеты.

{Программа составлена для решения задачи линейного программирования

 симплексным методом}

uses crt;

const n=2;{число неизвестных исходной задачи}

      m=3;{число ограничений}

      m1=0;{последняя строка равенств}

      m2=1;{последняя строка неравенств вида >=}

label 5,15,20,10;

var b,cb:array[1..m] of real;c,x,e:array[1..50] of real;a:array[1..m,1..50] of real;

    s0,max,mb,s1:real;i,j,k,i0,j0,m21,nm1,n1:integer; Bi:array[1..m] of integer;

begin

     clrscr;

     writeln;

     writeln (' Симплексный метод решения задачи линейного программирования:');

     writeln;

     writeln (' Проведем некоторые преобразования с данной задачей:');

     writeln;

     writeln (' Подготовьте матрицу: сначала равенства, потом неравенства вида >= и неравенства  вида <=;');

     writeln (' Целевая функция должна быть на минимум (привести ее к такому виду); ');

     writeln (' Вектор b должен состоять только из положительных элементов (привести его к та-  кому виду);');

     writeln(' Введите матрицу А ',m,'*',n,' построчно:');

     for i:=1 to m

         do begin for j:=1 to n

                      do read (a[i,j]);

                      readln

                  end;

     writeln (' Введите в виде строки вектор b, состоящий из ',m,' компонент:');

     for i:=1 to m

         do read (b[i]);

     writeln(' Введите теперь вектор с, состоящий из ',n,' компонент:');

     for i:=1 to n

          do read (c[i]);

     m21:=m2-m1+n;nm1:=n+m-m1;n1:=n+m-m1+m2;

     for i:=1 to m

         do for j:=n+1 to n1

                do a[i,j]:=0;

     {переход к равенствам в неравенствах >=}

     for i:=m1+1 to m2

         do a[i,n+i-m1]:=-1;

     {переход к равенствам в неравенствах <=}

     for i:=m2+1 to m

         do a[i,m21+i-m2]:=1;

     {создание искуственного базиса}

     for i:=1 to m2

         do a[i,nm1+i]:=1;

         {ввод mb в вектор с}

     mb:=12345;

     for i:=n+1 to nm1

         do c[i]:=0;

     for i:=nm1+1 to n1

         do c[i]:=mb;

     {выписать cb}

     for i:=1 to m2

         do begin cb[i]:=mb; Bi[i]:=nm1+i end;

     for i:=m2+1 to m

         do begin Bi[i]:=m21+i-m2;

                  cb[i]:=0;

            end;

     for i:=1 to n1

         do x[i]:=0;

     writeln(' Решение задачи:');

     {применяем симплексный метод, вычисляем оценки}

     5: for j:=1 to n1

            do begin s0:=0;

                     for i:=1 to m

                         do s0:=s0+cb[i]*a[i,j];

                     e[j]:=s0-c[j]

               end;

     max:=e[1];j0:=1;

     for i:=2 to n1

         do if e[i]>max

               then begin max:=e[i];

                          j0:=i

                    end;

     {получили столбец с максимальной оценкой}

     if max<=0

        then begin for i:=1 to m

                       do x[Bi[i]]:=b[i];

                                        goto 15

             end;

     s1:=a[1,j0];

     for i:=2 to m

         do if s1<a[i,j0]

               then s1:=a[i,j0];

     if s1<=0

        then goto 10;

     s1:=mb;

     for i:=1 to m

         do if a[i,j0]>0

               then if s1>b[i]/a[i,j0]

                       then begin

                                  s1:=b[i]/a[i,j0];

                                  i0:=i

                            end;

     {главный элемент a[i0,j0]}

     s0:=a[i0,j0]; Bi[i0]:=j0;

     for j:=1 to n1

         do a[i0,j]:=a[i0,j]/s0;

     b[i0]:=b[i0]/s0;

     for i:=1 to m

         do if i<>i0

               then begin s1:=-a[i,j0];

                          b[i]:=b[i]+b[i0]*s1;

                          for j:=1 to n1

                              do a[i,j]:=a[i,j]+a[i0,j]*s1

                    end;

      cb[i0]:=c[j0];

      goto 5;

      10: writeln(' Нет оптимального плана, функция неограничена');

      goto 20;

      {просмотр иск. переменных}

      15: for i:=nm1+1 to n1

              do if x[i]>0

                    then begin writeln(' Пустое множество планов');

                               goto 20

                         end;

      for i:=1 to n

          do writeln(' x[',i,']=',x[i]:7:4);

      20:readkey

end.

Содержание

Введение………………………………………………………………………………1                                                                                                                            

§1. Задача линейного программирования и свойства её решений…………….…4

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

      задачи линейного программирования……………………………………….…6

§3. Симплексный метод……………………………………………………………..8

§4. Понятие двойственности……………………………………………………….11

§5. Основные теоремы двойственности

      и их экономическое содержание………………………………………….……14

§6. Примеры экономических задач………………………………………………..16

§7. Анализ задачи об оптимальном использовании сырья………………………19

§8. Программа и расчеты…………………………………………………………..25