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

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.