Контрольная работа по «Прикладной математике»

Министерство  экономического развития Российской Федерации

Московский  Государственный  университет коммерции

Ростовский  институт (филиал) 
 
 
 
 
 
 

Контрольная работа 

по  дисциплине «Прикладная математика» 
 
 
 
 
 

                                                 Выполнила: Бражкина Вера А.

                                                                      Группа КФ-1 З/О

                                          Проверил:   Дерезина Н.П.  
 
 
 
 
 

Ростов-на-Дону

2011г. 

Задачa № 2.

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

Решение

     Построим на плоскости Х₁OХ₂  многоугольник решений рис 1. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств:

     Построив  полученные прямые, найдем соответствующие  полуплоскости и их пересечение:

      Рис 1. 

     Многоугольником решений задачи является пятиугольник АВСDЕ, координаты точек которого удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи.

Для нахождения точек экстремума построим начальную  прямую F(X)=0=14x₁+6x₂ и вектор N (14,6) Передвигая прямую F(X)-0 параллельно самой себе в направлении вектора N, найдем точку D,в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке D целевая функция принимает максимальное значение, так как точка D получена в результате пересечения прямых 1 и 5 , то ее координаты удовлетворяют уравнениям этих прямых: 

Решив систему уравнений, получим: x₁=0; x₂=7, а F(X)=14*0+6*7=42.

Для нахождения минимального значения целевой функции  задачи перемещаем начальную прямую в направлении, противоположном вектору N. Начальная прямая займет положение опорной прямой в вершине A. Целевая функция принимает минимальное значение в угловой точке A: 

где x₁=5/6=0,833, x₂=0,833,  а F(X)=14*0,833+6*0,833=16,66.

  Найдем координаты угловых точек:  В, С и Е. Для этого решим следующие системы уравнений: 

В результате получим координаты точек В(1;1), C(1;4,66) и E(0;5).

Вычислим  значения целевой функции во всех угловых точках многоугольника решений АВСDЕ: 

A(0,833;0,833), F(X)=14*0,833+6*0,833=16,66 (min),

В(1;1), F(X)=14*1+6*1=20,

C(1;4,66), F(X)=14*1+6*4,66=41.96,

D(0;7), F(X)=14*0+6*7=42(max),

E(0;5), F(X)=14*0+6*5=30. 

Задачa № 28

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b₁, b₂, b₃ единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a₁₁ единиц, ресурса второго вида в количестве a₂₁ единиц, ресурса третьего вида в количестве a₃₁ единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве  а₁₂, а₁₃ единиц, ресурсов второго вида в количестве а₂₂, а₂₃ единиц, ресурсов третьего вида в количестве а₃₂, а₃₃ единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c₁, c₂, с₃ (тыс. руб.).

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

а₁₁=16, a₁₂=18, a₁₃=9, a₂₁=7, а₂₂=7, а₂₃=2, а₃₁=9, a₃₂=2, а₃₃=3, b₁=520, b₂=140, b₃=810, с₁=8, c₂=6, c₃=4. 

Решение 

Для решения  задачи симплексным методом построим таблицу затрат и объёма ресурсов:

Таблица 1

1. Запишем  математическую модель задачи.

Определить  X =(х₁,х₂,х₃), который удовлетворяет условиям

И обеспечивают максимальное значение целевой функции:

Для построения первого опорного плана систему  неравенств приведем к системе уравнений. 

В матрице  этой системы уравнений  А(а_ij) имеет: 
 

Векторы A₄, A₅, A₆, - линейно независимы, так как определитель, составленный из компонент этих векторов, отличных от нуля: 

Решим систему уравнений относительно базисных переменных. 

Функцию цели запишем в виде: 

2. Полагая, что свободные переменные x₁=0, x₂=0, х₃=0, получим первый опорный план X₁=(0,0,0,520,140,810), F(X₁)=0, в котором базисные переменные x₄=520, х₅=140, x₆=810, следовательно, товары не продаются и прибыль равна нулю, а ресурсы не используются.

Заносим первый опорный план 1 в симплексную таблицу 2

Таблица 2 

3. Первый  опорный план I не оптимальный,  так как в индексной строке находятся отрицательные коэффициенты  -8, -6, -4.

4. За  ведущий столбец выберем столбец,  соответствующий переменной х₁, так как сравнивая по модулю имеем:

|-8| > {|-6|, |-4|} Рассчитываем  значения  по строкам, как частное от деления 

 и выбираем наименьшее:

Следовательно, вторая строка является ведущей

Разрешающий элемент равен 7 и находится на пересечении ведущего столбца и ведущей строки и выделен квадратом.

5. Формируем  следующую симплексную таблицу. Вместо переменной х₅ в план II войдет переменная х₁. Строка, соответствующая переменной х₁ в плане II, получена в результате деления всех элементов строки х₅ плана I на разрешающий элемент РЭ=7.  На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х₁ плана II записываем нули.

Таким образом в новом плане II заполнены строки х₁ и столбец х₁. Все остальные элементы нового плана II, включая элементы индексной строки определяется по правилу прямоугольника. Для этого выбираем из старого плана 4 числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=8. Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции F(X₁)=0=СЭ, которое указывает на место расположение нового НЭ в новом плане II. Третий элемент А=140 и четвертый элемент В=-8 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:

                                          140* (-8)

НЭ=СЭ - (А - В)/РЭ=0-       7       =160.

Элементы  строки определяются аналогично 

      140* 16

520 -    7        =200, 
 

          16* 7

18 -      7        =2, 
 

          16* 2

9 -       7        =4,429, 
 

         1* 16

0 -      7        =-2,286. 
 

Все элементы, расположенные на пересечении строк  и столбцов, соответствующих одноименным базисным элементам равны 1,  а элементы образующие квадрат – 0, следовательно, значений они не меняют.

6. План II не является оптимальным, так как есть коэффициенты в индексной строке < 0.

7. Аналогично получаем план III. Он оптимален, так как индексные коэффициенты > 0.

Его можно записать так:

X=(7,097;0; 45,161;0; 0; 610,645),                                                                                                                                                                                                                  F( X ^*)=237,419 тыс. руб.

Следовательно, необходимо продавать товаров первой группы  7,097 ед., а третьей группы 45,161. При этом торговое предприятие получает максимальную прибыль в размере 237,419 тыс. руб. Товары второй группы не реализуются.

В оптимальном  плане среди базисных переменных находится дополнительная переменная x₆. Это указывает, что ресурсы третьего вида недоиспользованы на 610,645 ед., так как переменная х₆ была введена в третье ограничение.

В индексной  строке оптимального плана в столбцах переменных x₂, x₄, x₅, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным.

Задача  № 51

Используя вариант предыдущего  контрольного задания  № 28, необходимо:

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

установить  сопряженные пары переменных прямой и  двойственной задач,

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

Решение 

Определим Y = (y₁, у₂, y₃), который удовлетворяет условиям - ограничениям: 

и обеспечивает минимальное значение целевой функции:  

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

Y° = (0,387; 0,258; 0; 0; 2,774; 0)        Z(Y°) =237,419. 

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

Задача № 76

     Поставщики товара - оптовые коммерческие предприятия А₁, А₂,…, А_m, имеют запасы товаров соответственно в количестве а1, а2,...,

a_п, ед. и розничные торговые предприятия В₁,В₂,…,В_n, подали заявки на закупку товаров в объемах соответственно: b1 b2, b3,...,bп. Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы.

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

     a₁=222, b₁=125,

     a₂=188, b₂=75,

     a₃=210, b₃=200,

     a₄=380, b₄=380,

     b₅=220, 

Решение

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

Как видно, суммарная потребность груза  в пунктах назначения равна запасам груза на четырех базах. Следовательно, модель исходной транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу 3.

Таблица 3. Опорный план I.

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

Среди тарифов из всей таблицы первым наилучшим является с₂₄ =2, поэтому в клетку A₂B₄ направляем максимально возможный груз. Он равен min{188,380}=188. Тогда х₂₄=188 и из базы A₂ вывезен весь груз, а потребность пункта В₄, удовлетворена не полностью, на 188 ед. и в него необходимо поставить 380-188=192 ед. товара. Строка А₂ выходит из рассмотрения. Из оставшихся тарифов наименьший – с₃₁=2. В клетку A₃B₁ направляем максимально возможный груз, равный min{210,125}= 125 и х₃₁=220. Тогда в строке A₃ остается 210-125=85 ед., а потребность столбца В₁ удовлетворена полностью и он выходит из рассмотрения. Из оставшихся тарифов наименьший – с₁₅=3. В клетку A₁B₅ направляем максимально возможный груз, равный min{222,220}= 220 и х₁₅=220. Тогда в строке A₁ остается 222-220=2 ед., а потребность столбца В₅ удовлетворена полностью и он выходит из рассмотрения. Среди тарифов из всех оставшихся наилучшим является с₃₄ =4, поэтому в клетку A₃B₄ направляем максимально возможный груз. Он равен min{85,192}=85 (остатки товара и потребностей). Тогда х₃₄=85 и из базы A₃ вывезен весь груз, но потребность пункта В₄, удовлетворена не полностью, а на 85 ед. и в него необходимо поставить 192-85=107 ед. товара. Строка А₃ выходит из рассмотрения. Далее: наилучшим является с₁₄ =8, поэтому в клетку A₁B₄ направляем максимально возможный груз. Он равен min{2,107}=2 (остатки товара и потребностей). Тогда х₁₄=2 и из базы A₁ вывезен весь груз, но потребность пункта В₄, удовлетворена не полностью, а на 2 ед. и в него необходимо поставить ещё 107-2=105 ед. товара. Строка А₁ выходит из рассмотрения. Из оставшихся тарифов наименьший – с₄₄=8. В клетку A₄B₄ направляем максимально возможный груз, равный min{380,105}= 105 (остаток потребности В₄) и х₄₄=105. Тогда в строке A₄ остается 380-105=275 ед., а потребность столбца В₄ удовлетворена полностью и он выходит из рассмотрения. Осталось два столбца и из них наилучший тариф – с₄₂=9. В клетку A₄B₂ направляем максимально возможный груз, равный min{275,75}= 75  и х₄₂=75. Тогда в строке A₄ остается 275-75=200 ед., а потребность столбца В₂ удовлетворена полностью и он выходит из рассмотрения. Остатки ресурсов и потребностей равны, и записываются в единственную доступную клетку А₄В₃, где с₄₃=21, и х₄₃=200. В результате получен первый опорный план, который является допустимым, так как все грузы из пунктов вывезены, потребность удовлетворена, а план удовлетворяет системе ограничений транспортной задачи. Построение опорного плана I окончено.

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

3. Определяем значение целевой функции первого опорного плана 

F(X)=2*8+220*3+188*2+125*2+85*4+75*9+200*21+105*8=7357. 

Проверим  оптимальность опорного плана. 

4.Найдем  потенциалы α_i β_j, по занятым клеткам таблицы, решая систему уравнений, полагая α_i+ β_j = c_ij и α₁= 0: 
 

5. Занесем рассчитанные потенциалы в таблицу 3.- подсчитаем оценки     свободных     клеток,     полагая     что    для     них Δ_ij=c_ij – (α_i+ β_j):

Δ₁₁=23-6=17; Δ₁₂=21-9=12; Δ₁₃=11-21=-10;

Δ₂₁=7-0=7; Δ₂₂=17-3=14; Δ₂₃=5-15=-10; Δ₂₅=4+3=7;

Δ₃₂=16-5=11; Δ₃₃=8-17=-9; Δ₃₅=3+1=4;

Δ₄₁=3-6=-3; Δ₄₅=4-3=1;

Первый  опорный план является не оптимальным, так как Δ₁₃<0, Δ₂₃<0, Δ₃₃<0, Δ₄₁<0,  поэтому переходим к его улучшению. Выбираем максимальную по модулю оценку свободной клетки – Δ₂₃=| - 10| = 10.

6. Для клетки А₂В₃ построим цикл перераспределения груза. Для этого в перспективную клетку A₂B₃ поставим знак +, а в остальных вершинах многоугольника чередующиеся знаки -,+,-.

А₂В₃                         А₂В₄

   +                   - 
 
 

А₄В₃                А₄В₄

    -      +

Затем из чисел x_ij, стоящих в минусовых клетках, выбираем наименьшее, т е min{188,200}= 188, Прибавляем 188 к объемам грузов, стоящих в плюсовых клетках и вычитаем 188 из x_ij, стоящих в минусовых клетках. В результате получим новый опорный план II. 

Таблица 4. Опорный план II.

7. Определяем значение целевой функции II опорного плана 

F(X₂)=F(X) +(-10)*188=7357- 1880=5477. 

Проверим  оптимальность опорного плана. 

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

9. Найдем потенциалы α_i, β_j, по занятым клеткам таблицы, решая систему уравнений, полагая α_i+ β_j = c_ij и α₁= 0:

10. Занесем рассчитанные потенциалы в таблицу 4.- подсчитаем оценки     свободных     клеток,     полагая     что    для     них Δ_ij=c_ij – (α_i+ β_j):

Δ₁₁=23-6=17; Δ₁₂=21-9=12; Δ₁₃=11-21=-10;

Δ₂₁=7+10=17; Δ₂₂=17+7=24; Δ₂₄=2+8=10; Δ₂₅=4+13=17;

Δ₃₂=16-5=11; Δ₃₃=8-17=-9; Δ₃₅=3+1=4;

Δ₄₁=3-6=-3; Δ₄₅=4-3=1;

Второй опорный план является не оптимальным, так как Δ₁₃<0, Δ₃₃<0, Δ₄₁<0,  поэтому переходим к его улучшению. Выбираем максимальную по модулю оценку свободной клетки – Δ₁₃=| - 10| = 10.

11. Для клетки А₁В₃ построим цикл перераспределения груза. Для этого в перспективную клетку A₁B₃ поставим знак +, а в остальных вершинах многоугольника чередующиеся знаки -,+,-.

А₁В₃                         А₂В₄

   +                   - 
 
 

А₄В₃                А₄В₄

    -      +

Затем из чисел x_ij, стоящих в минусовых клетках, выбираем наименьшее, т е min{2,12}= 2, Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из x_ij, стоящих в минусовых клетках. В результате получим новый опорный план III.

Таблица 5. Опорный план III.