Контрольная работа по "Программированию и компьютеру". 2

Содержание 

1. Система переменных и система ограничений ЭММ оборота стада сельскохозяйственных животных.        3

2. Задание 2. Транспортная задача        6

3. Задание 3. Разработка модели производственно-отраслевой структуры организации           10

4. Задание 4. Решение задачи линейного программирования графическим методом            13

5. Задание 5. Решение  задач линейного программирования  модифицированным симплексным методом          15

Список  литературы          17

1. Система переменных и система ограничений ЭММ оборота стада сельскохозяйственных животных 

     Система переменных  включает следующие  группы:

     1) по численности поголовья сельскохозяйственных  животных по их половозрастным  группам (по КРС – коровы, нетели, телки рождения прошлого года, телки рождения позапрошлого года, быки-производители, телята на выращивании и откорме, взрослый скот на откорме, телята до отъема) на начало и конец планируемого периода;

      2) по поголовью сельскохозяйственных  животных, переводимых из одних  групп в другие;

      3) по иным видам движения и использования поголовья сельскохозяйственных животных;

     4) дополнительные переменные, отражающие  и ограничивающие отклонение  численности поголовья в группах; 

     5) прочие дополнительные переменные (например, по объемам производства  продукции животноводства, по определению среднегодового поголовья животных в группах);

      6) вспомогательные переменные.

     Система ограничений  оптимизации оборота  стада включает следующие группы:

      1. По поголовью животных на  начало планируемого периода.  Общий вид матзаписи:

Х_hн=b_hн (h€H),

      где Х_hн – переменная, отражающая поголовье h-й половозрастной группы животных на начало периода;

      b_hн – поголовье h-й половозрастной группы животных на начало периода;

      h – порядковый номер h-й половозрастной группы животных;

     H – множество половозрастных групп животных, рассматриваемых в модели.

     2. По сбалансированности движения  поголовья животных (в каждой  половозрастной группе сумма  количества животных на начало  периода и количества поступивших  в группу должна быть равна  сумме количества животных на конец года и количества выбывших из группы). Общий вид матзаписи:

Х_hн+X_(h-1)д+∑X_th=X_hк+X_(h+1)д+∑X_fh (h, (h-1), (h+1)€H; t€T; f€F)

      X_hк – переменная, отражающая поголовье животных h-й половозрастной группы на конец периода;

      X_(h-1)д, X_(h+1)д – переменные, отражающие количество животных переведенных из группы в группу, соответственно из младшей группы в h-ю и из h-й группы в старшую;

      X_th – переменная, отражающая количество животных поступивших в h-ю половозрастную группу из t-го источника;

      X_fh – переменная, отражающая количество животных выбывших из h-й половозрастной группы в f-м направлении использования;

t – источники поступления животных (покупка (t=1), приплод (t=2) и т. д.);

f – направление использования животных (продажа (f=1), выбраковка на откорм и последующий убой (f=2), падеж (f=3) и т. д.);

T – множество источников поступления животных;

F – множество направлений использования животных.

     3. По соотношению между поступлением  животных в старшие группы  и переводом из младших. Общий  вид матзаписи:

X_(h-1)д= (≥≤) X_(h+1)д (h, (h-1), (h+1)€H).

     1. Здесь возможно использование  коэффициентов соотношения. 

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

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

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

Х_hн = (≤≥)X_hк (h€H) – по отдельным половозрастным группам;

∑Х_hн = (≤≥)∑X_hк (h€H) – по суммарному поголовью.

     5. По предельным объемам различного  рода поступления и выбытия  животных. Общий вид матзаписи по покупке животных:

X_th =(≥≤)b_th (h€H; t=1),

b_th – предельный объем покупки животных h-й половозрастной группы.

     По  реализации животных:

X_fh =(≥≤)b_fh (h€H; f=1),

b_fh – предельный объем продажи животных h-й половозрастной группы.

     По  выбраковке (падежу) животных:

X_fh =(≥≤)d_h (X_hн+X_hк) (h€H; f=2,3),

     где d_h – коэффициент выбраковки (падежа) h-й половозрастной группы животных на откорм и последующий убой.

     6. По предельным объемам производства  и реализации продукции животноводства. Общий вид матзаписи по выходу приплода:

X_th = w_h (∑X_hн+∑X_hк)  (h€H_м, t=2),

      где w_h – выход приплода (обоего пола) на одну голову маточного поголовья. Далее при включении приплода в оборот стада следует учитывать его распределение по полу;

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

     По  выходу продукции с животных на убой, выбраковку (мясо, шкуры):

X_p=∑q_pfh X_fh (p – вид продукции (мясо, шкуры); f=2,3; h€H),

X_p – дополнительная переменная, отражающая объем производства p-го вида продукции (мясо, шкуры);

q_pfh – выход p-го вида продукции с одной головы h-й группы животных f-го направления использования.

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

X_hср=0,5(X_hн+X_hк),

X_hср – вспомогательная переменная, отражающая среднегодовое поголовье животных в h-й половозрастной группе.

     Общий вид матзаписи выхода продукции  с оборота стада (молока, привеса  живой массы, шерсти и т. д.):

X_p = q_phX_hср,

q_ph – выход p-го вида продукции с одной головы h-й группы животных.

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

Задание 2. Транспортная задача 

      В четырех пунктах отправления имеется груз в следующем количестве: первый пункт отправления -190, второй – 230, третий – 200, четвертый – 230 тонн. Его необходимо доставить в четыре пункта назначения в следующем количестве: первый пункт назначения – 160, второй – 240, третий – 270, четвертый – 320 тонн. Требуется составить план перевозок с минимумом затрат на транспортировку. Расстояние между пунктами отправления и назначения в км приведены в таблице. 

Решение: 

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

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

 ∑ a = 160 + 240 + 270 + 320 = 850

 ∑ b = 190 + 230 + 200 + 230 = 990

        Как видно, суммарная потребность  груза в пунктах назначения  превышает запасы груза на  базах. Следовательно, модель  исходной транспортной задачи  является открытой. Чтобы получить  закрытую модель, введем дополнительную (фиктивную) базу с запасом  груза, равным 140 (990-850). Тарифы перевозки единицы груза из базы во все магазины полагаем, равны нулю.

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

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

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

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

        3. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₂ + v₄ = 3; 2 + u₂ = 3; u₂ = 1

u₂ + v₁ = 2; 1 + v₁ = 2; v₁ = 1

u₄ + v₄ = 6; 2 + u₄ = 6; u₄ = 4

u₄ + v₃ = 2; 4 + v₃ = 2; v₃ = -2

u₄ + v₅ = 0; 4 + v₅ = 0; v₅ = -4

u₃ + v₅ = 0; -4 + u₃ = 0; u₃ = 4

u₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1 
 
 

      Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(3;1): 4 + 1 > 4; ∆₃₁ = 4 + 1 - 4 = 1

(4;1): 4 + 1 > 3; ∆₄₁ = 4 + 1 - 3 = 2

        Выбираем максимальную оценку  свободной клетки (4;1): 3

        Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 

        Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план. 

       4. Проверим оптимальность опорного  плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₂ + v₄ = 3; 2 + u₂ = 3; u₂ = 1

u₂ + v₁ = 2; 1 + v₁ = 2; v₁ = 1

u₄ + v₁ = 3; 1 + u₄ = 3; u₄ = 2

u₄ + v₃ = 2; 2 + v₃ = 2; v₃ = 0

u₄ + v₅ = 0; 2 + v₅ = 0; v₅ = -2

u₃ + v₅ = 0; -2 + u₃ = 0; u₃ = 2

u₃ + v₂ = 5; 2 + v₂ = 5; v₂ = 3 

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

        Затраты составят:

F(x) = 2*160 + 2*170 + 3*70 + 5*230 + 0*40 + 3*20 + 2*200 + 0*100  = 2480 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Задание 3. Разработка модели производственно-отраслевой структуры организации 

      Площадь пашни в сельскохозяйственной организации составляет 2800 га, сенокосов – 700 га, пастбищ – 300 га. В хозяйстве возделываются пшеница, озимая рожь, ячмень, свекла и картофель, животноводческий подкомплекс включает коров, молодняк КРС и свиней. Для содержания одной коровы требуется 1,8 га пашни, 0,7 га сенокосов и 0,2 га пастбищ, молодняка КРС – 1,1 га пашни, 0,3 га сенокосов, 0,1 га пастбищ, овец - 0,6 га пашни. При необходимости не более 200 га сенокосов может быть трансформировано в пашню. Площадь посевов свеклы не должна превышать 66% от площади картофеля. Площадь посевов озимых зерновых не должна превышать 70% от яровых зерновых и не должна превышать 20% от площади пашни. Хозяйство располагает трудовыми ресурсами в размере 200 тыс. чел.-ч. Затраты труда составляют на 1 га посевов пшеницы - 3 чел.-ч., озимой ржи - 2, ячменя -2, свеклы - 80, картофеля - 90 чел.-ч., а на одну голову молодняка КРС - 100, корову - 200, голову свиней - 80 чел.-ч. Объем производства молока в хозяйстве должен быть не менее 2000 ц и не более 5000 ц, мяса - не менее 400 ц. Продуктивность животных на одну голову: свиней - 0,9 ц мяса, коров -30 ц молока, молодняка КРС - 20 ц мяса. Поголовье коров в структуре стада КРС должно быть не более 39%. Стоимость товарной продукции составляет с 1 га пшеницы — 7,2, озимой ржи — 6,3, ячменя — 5,6, свеклы — 9,2, картофеля - 13,3 тыс. руб., с одной головы свиней - 6, коров - 14,5, молодняка КРС - 12,1 тыс. руб. Требуется разработать экономико-математическую модель производственно-отраслевой структуры и ее матрицу. Критерий оптимальности – максимум стоимости товарной продукции. 

Решение: 

Система переменных.

х₁ – площадь пшеницы;

х₂ – площадь озимой ржи;

х₃ – площадь ячменя;

х₄ – площадь свеклы;

х₅ – площадь картофеля;

х₆ – поголовье коров;

х₇ – поголовье молодняка КРС;

х₈ – поголовье свиней;

х₉ – площадь сенокосов;

х₁₀ – площадь пастбищ; 

Система ограничений

I. Блок ограничений  по использованию  производственных  ресурсов:

Пашня

     х₁ + х₂ + х₃ + х₄ + х₅ £ 2800 га

1) При  необходимости не более 200 га  сенокосов может быть трансформировано  в пашню.

     х₁ + х₂ + х₃ + х₄ + х₅ + х₉  £ 2800 + 700 - 200 га

2) Сенокосы

     х₉ £ 700  га

3) Пастбища

      х₁₀ £ 300 га

4) Трудовые  ресурсы

     3х₁ + 2х₂ + 2х₃ + 80х₄ + 90х₅ + 200х₆ + 100х₇ + 80х₈  £  200 000

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

5) Площадь посевов свеклы не должна превышать 66% от площади картофеля.

      х₄ £ 0,66х₅

     преобразим  и приведем к нулю:

х₄ - 0,66х₅ £ 0

Площадь посевов озимых зерновых не должна превышать 70% от яровых зерновых и не должна превышать 20% от площади пашни..

6) х₂ £ 0,7х₁