Организация оплаты труда

рациональной перевозке  некоторого однородного продукта от производителей к

потребителям; при этом имеется  баланс между суммарным спросом  потребителей и

возможностями поставщиков  по их удовлетворению. Причем по­требителям

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

их заявки были полностью  удовлетворены. Так как от схемы  прикрепления

потребителей к поставщикам  существенно зависит объем транспортной работы,

возникает задача о наиболее рациональном прикреплении, правильном

направлении перевозок грузов, при котором потребности полностью

удовлетворяются, вся продукция  от поставщиков вывозится, а затраты  на

транспортировку минимальны.

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

Речь идет о задаче распределения  заказа (загрузки взаимозаменяемых групп

оборудования) между предприятиями (цехами, станками, исполнителями) с

различными производственными  и технологическими характеристиками, но

взаимозаменяемыми в смысле выполнения заказа. Требуется составить  план

размещения заказа (загрузки оборудования), при котором с имеющимися

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

эффективности достигал экстремального значения.

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

Исходя из специализации  и своих технологических возможностей  предприятие

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

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

станочное оборудование. Общий  объём ресурсов, расход каждого ресурса  за

единицу продукции, приведены  в таблице 1. Требуется определить план выпуска,

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

анализ решения и параметров модели.

     Ресурсы Выпускаемая продукция 

Объём

 

Ресурсов

 

 

 

 

 

 

Трудовые  ресурсы, чел-ч 4 2 2 8 4800

 

Полуфабрикаты, кг 2 10 6 0 2400

 

Станочное оборудование, станко-ч 1 0 2 1 1500

Цена единицы продукции, р. 65 70 60 120 

 

 

 

 

                                    Решение.                                   

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

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

    

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

    

    

    

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

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

максимум реализации (максимум выручки)

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

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

таблице1.

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

опорный план является оптимальным:

, 

Основные переменные

показывают, что продукцию

и  выпускать

нецелесообразно, а продукции 

следует произвести 400 ед.,

- 500 ед.

Дополнительные переменные

и  показывают, что

ресурсы используются полностью 

, а вот равенство  

свидетельствует о том, что 200 единиц продукции 

осталось неиспользованным.

     Номера ит. БП Сб 

 

 

 

 

 

 

 

 

65 70 60 120 0 0 0

0 

0 4800 4 2 2 8 1 0 0

 

0 2400 2 10 6 0 0 1 0

 

0 1500 1 0 2 1 0 0 1

 

0 -65 -70 -60 -120 0 0 0

1 

120 600 1/2 1/4 1/4 1 1/8 0 0

 

0 2400 2 0 6 0 0 1 0

 

0 900 1/2 -1/4 7/4 0 -1/8 0 1

 

72000 -5 -40 -30 0 15 0 0

2 

120 500 5/12 -1/6 0 1 1/8 -1/24 0

 

60 400 1/3 5/3 1 0 0 1/6 0

 

0 200 -1/12 -19,6 0 0 -1/8 -7/24 1

 

84000 5 10 0 0 15 5 0

 

 

Выпишем из таблицы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