Содержание 
 

 

Задача 1

 

      Полуфабрикаты поступают на предприятие в виде листов фанеры. Всего имеется две  партии материала, причем первая партия содержит 400 листов, а вторая – 250 листов. Из поступающих листов фанеры необходимо изготовить комплекты, включающие 4 детали 1 вида, 3 детали 2 вида, и 2 детали 3 вида. Лист фанеры каждой партии может раскраиваться различными способами. Количество деталей каждого типа, которое получается при раскрое одного листа соответствующей партии по тому или иному способу раскроя, представлено в таблице. Требуется раскроить материал так, чтобы обеспечить изготовление максимального числа комплектов.

Решение

 

     Обозначим через х_ij число единиц из i-й партии (1,2) фанеры, которые намечено раскроить j -м способом (1,2,3) , так что из i -й партии при j -м способе раскроя будет получено а_ijkх_ij деталей к -го вида. Всего из всей i -й партии деталей к -го вида будет получено , а из всех m партий их будет получено:

     Из  первой партии фанеры:

     Деталей первого вида: 400(0х₁₁+6х₁₂+9х₁₃)

     Деталей второго вида: 400(4х₁₁+3х₁₂+4х₁₃)

     Деталей третьего вида: 400(10х₁₁+16х₁₂+0х₁₃)

     Из  второй партии фанеры:

     Деталей первого вида: 250(6х₂₁+5х₂₂)

     Деталей второго вида: 250(5х₂₁+4х₂₂)

     Деталей третьего вида: 250(8х₂₁+0х₂₂)

     Всего из двух партий фанеры:

     Деталей первого вида: 400(6х₁₂+9х₁₃)+ 250(6х₂₁+5х₂₂)

     Деталей второго вида: 400(4х₁₁+3х₁₂+4х₁₃)+ 250(5х₂₁+4х₂₂)

     Деталей третьего вида: 400(10х₁₁+16х₁₂)+ 2000х₂₁

     Число полных комплектов, которое можно  выпустить по данному плану, будет  равно:

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

     z = x  →   min,

      при ограничениях:

     

     

     

     х₁₁+х₁₂+х₁₃=400

     х₂₁+х₂₂+х₂₃=250

      ,     где х, х_ij – целые числа.

Задача 2

 

      Решить  графическим методом.

      Решить  графическим методом

      Z= 3 х₁-4х₂   → max при условиях:

      -х₁ +х₂≤1

      -х₁ +2х₂≥-2

      х₁ +х₂≥-1

      -3х₁+2х₂ ≤6;

      2х₁– х₂≤2

      х₁ ≥0; х₂≥0

Решение

 

      Запишем ограничения в виде равенств и  построим соответствующие им линии уровня в системе координат. Строим область допустимых значений решения, удовлетворяющую начальным условиям. Семи заданным неравенствам соответствует множество точек плоскости, образующие пятиугольник АВСDE. Неравенства х₁ ≥-4; х₁ +5х₂≥4 могут быть исключены, так как они определяют граничные прямые, не имеющие с АВСDE общих точек.

      Строим  на плоскости вектор целевой функции  . Через начало координат перпендикулярно проводим линию уровня целевой функции Z=0. Линия уровня перемещается в направлении параллельно самой себе, пока не встретится с вершиной области допустимых значений АВСО  т. В.  Значение  Z в точке В является минимальным.

      При дальнейшем перемещении линия уровня пройдет через другую вершину ОДР, выходя из области решений – точку С. Значение  Z в точке С является максимальным. Значение целевой функции Z_mах  в т. С. Найдем её координаты:  

       2х₁– х₂ =2        

      х₂=0

      С(0;  1)

      Z_mах=3*1-4*0=3

      Ответ: Z_mах=3.

        

Задача 4

 

      Удельные  затраты С_ij на перевозку 1 т груза вида i транспортом j (руб.) представлены матрицей

      С_ij=

Мощности  поставщиков А₁=30 тыс.т; А₂=10 тыс.т; А₃=40 тыс.т; А₄=70 тыс.т. Спрос потребителей: В₁=30 тыс.т; В₂=10 тыс.т; В₃=20 тыс.т; В₄=10 тыс.т.

Определить  объемы перевозок груза транспортом  j (руб.), чтобы суммарные издержки были бы минимальными, построить матрицу объемов перевозок.

Решение

 

      1. Определяем тип задачи. Так как  .     Задача является открытой. Введем фиктивного потребителя с объемом потребления В_ф.

      2. Строим расчетную матрицу с  фиктивным потреблением В_ф  и удельными затратами на перевозку фиктивного груза С_iф=0.

      3. Сформируем опорный план по  критерию наименьших удельных затрат на перевозку единицы груза ,  т. е.  min С_iф.

Оставшиеся  мощности относятся к фиктивному потребителю: х_iф=А_ii-

Опорный план

      4. Проверим полученный план перевозок  на вырожденность. Так как 

      4 столбца + 5 строк-1 > 7 поставок. То задача вырожденная. Для приведения плана к невырожденному состоянию введем в клетки (4;2) и (1,4) фиктивные нулевые поставки.

      5. Оптимизируем план, используя метод  потенциалов.

      С_ij= U_i+ V_j, где U_i– потенциал строки; V_j– потенциал столбца.

      Пусть V₄=0. пересчитаем все остальные U_i и V_j и зафиксируем их в опорном плане.  U₄=1,2; V_ф =0; V₄ =0-1,2=-1,2; V_ф=0-1,2=-1,2; U₃ =0-(-1,2)=1,2; V₃=1,2-1,2=0; U₁ =1,5-0=1,5; V₁ =1,2-1,5=-0,3; V₂ =0; U₂ =1-0=1.

      6. Определяем характеристики свободных  клеток: Е_ij= С_ij-(U_i+ V_j)≥0.

      Е₁₂=1,6-0-1,5=0,1; Е₁₃=1,7-0-1,5=0,2; Е_1ф=1,2-1,5=-0,3; Е₂₁=1,4+0,3-1=0,7; Е₂₃=1,2-1=0,2;  Е₂₄=1,5-1=0,5;  Е_2ф=0+1,2-1=0,2; Е₃₁=1,6+0,3-1,2=0,7; Е₃₂=1,4-0-1,2=0,2; Е₃₄=1,4-0-1,2=0,2; Е₄₁=1,5+0,3-1,2=0,5; Е₄₃=1,4-0-1,2=0,2.

      7. Характеристики клеток (3,ф) и (4,2) отрицательны, следовательно найденное решение не является оптимальным. Оптимизируем план. Для клетки к (1,ф) строим контур перераспределения.

      х_1ф= min{0; 60}=60

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

      Характеристики  свободных клеток матрицы неотрицательны, следовательно найденное решение  является оптимальным.

      Задача  решена.

        Определим значение целевой функции: 

      F=30*1,2+10*1+20*1,2+1,2*10=82 (тыс.р.)

Задача 5

 

      Для расчета мощности i-го вида транспорта необходимо воспользоваться значениями: S= 2 смены; z=8 часов; d= 25 дней.

      Представлена  грузоподъемность транспорта Р₁=10т; Р₂=5т; Р₃=10т; Р₄=15т.

      АТП располагает m=4 видами транспортных средств различной грузоподъемности. Их количество n₁=20; n₂=30; n₃=30; n₄=20. На j-й вид продукции приходится Вj(m) спрос: В₁= 120 тыс.р.; В₂= 50 тыс.р.; В₃= 80 тыс.р.; В₄= 100 тыс.р. Известно, что среднее время транспортировки для каждого вида транспорта и вида груза:

      Т=

      Даны  себестоимости перевозок j-го груза i-ым видом транспорта.

      С=

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

Решение

 

      1. Определяем мощность  А_i=d t S n_i

      d– количество рабочих дней (d=25) в месяце;

      t – количество часов в смене (t=8);

      S– количество смен (S=2) в сутки

      n_i– количество машин i-го типа.

      А₁=25*8*2*20=8000 маш.ч.; А₂=25*8*2*30=12000 маш.ч.; А₃=12000 маш.ч.; А₄=8000 маш.ч.

      2. Рассчитаем показатель удельной  производительности (т/маш.ч.); λ_ij=P_i/t_ij.

      λ=

      3. Рассчитаем критерий формирования  опорного плана: k_ij= λ_ij/ С_ij.

      K=

      4. Строим опорный план перевозок,  клетки распределения выбираем  по max k_ij. Это клетки Х₃₁и Х_43.

      Расчетная матрица