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

 

       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х₁