1) Выберем переменными задачи x1 – изделий вида А1; x2 – изделий вида А2.
Составим систему ограничений в виденеравенств
/>
Составим целевую функцию z(x) = 25·x1 + 17·x2 > max, т.е. обеспечить максимальную выручку от реализацииготовой продукции.
2) Найдем решение сформулированной задачи, используяее геометрическую интерпретацию. Сначала определим многоугольник решений. Дляэтого в неравенствах системы ограничений и условиях неотрицательностипеременных знаки неравенств заменим на знаки точных равенств и найдемсоответствующие прямые
/>
Эти прямые изображены на рис. 1. Пересечениеполученных полуплоскостей и определяет многоугольник решений данной задачи.
/>
Рис. 1. Графическое представление математическоймодели
Как видно из рис. 1, многоугольником решенийявляется пятиугольникОАВСD. Координатылюбой точки, принадлежащей данному пятиугольнику, удовлетворяют данной системенеравенств и условию неотрицательности переменных. Поэтому сформулированнаязадача будет решена, если мы сможем найти точку, принадлежащую пятиугольникуОАВСD, в которой функция z принимает максимальное значение. Чтобы найти указаннуюточку, построим вектор />, перпендикулярный прямой 25·x1 + 17·x2 = h, где h – некотораяпостоянная такая, что данная прямая имеет общие точки с многоугольникомрешений.
Перемещая, данную прямую в направлении вектора />, видим, чтопоследней общей точкой ее с многоугольником решений задачи служит точка B. Координаты этой точки и определяют план производствапродукции, при котором выручка от их реализации будет максимальной.
Находим координаты точки Cкак координаты точки пересечения прямых 8·x1+ 6·x2 = 848 и 5·x1+ 2·x2 = 432.
Решив эту систему уравнений,получим />, />. Итак, выручкаот реализации будет наибольшей, если в плане по производству содержится выпуск 64изделий А1 и 56 изделий А2, и, составляет 25·64 + 17·56 = 2552ден. ед.
3) Запишем данную задачу в формеосновной задачи линейного программирования. Для этого от ограничений-неравенствперейдем к ограничениям-равенствам. Введем три дополнительные переменные, врезультате чего ограничения запишутся в виде системы уравнений
/>
Составляем таблицу первой итерации:
/>
Базисные
переменные 25 17
/>
/>
/>
/>
/>
/>
/>
/>
848
532
432
8
3
5
6
5
2
1
1
1
/> -25 -17
В 4-й строке табл. в столбцахпеременных />,/>, имеютсяотрицательные числа. Наличие этих чисел говорит о том, что данный план неявляется оптимальным. Переходим к новому плану задачи: разрешающий элементвыделен (здесь и далее) подчеркиванием.
Вторая итерация
/>
Базисные
переменные 25 17
/>
/>
/>
/>
/>
25
/>
/>
/>
784/5
1364/5
432/5
1
14/5
19/5
2/5
1
1
-8/5
-3/5
1/5
/> 2160 -7
Третья итерация
/>
Базисные
переменные 25 17
/>
/>
/>
/>
/>
17
25
/>
/>
/>
56
60
64
1
1
5/14
-19/14
-1/7
1
-4/7
11/7
3/7
/> 2552
5/2
1
Из табл. видно, что найденный новыйопорный план исходной задачи X* = (64;56; 0; 60; 0) является оптимальным. Приэтом max z = 2552.
Итак, выручка от реализации будетнаибольшей, если в плане по производству содержится выпуск 64 изделий А1и 56 изделий А2, и, составляет 2552 ден. ед.
4)Для данной задачи />, тогда />. Число переменных в двойственнойзадаче равно числу уравнений в исходной задаче, т.е. 3. Коэффициенты в целевойфункции двойственной задачи являются свободными членами неравенств-ограничений,т.е. числами 848, 532, 432. Т.к., в исходной системе ограничения представленынеравенствами, то в двойственной задаче переменные /> являются неотрицательными.
Следовательно, двойственная задачатакова: найти минимум функции z*(x) = 848·y1 + 532·y2 + 432·y3 при условиях
/>
Из последней симплекс-таблицы (итерация3) видно, что двойственная задача имеет решение />, />, />.
1) Распределительный метод
Примем некоторые обозначения: i — индекс строки j — индекс столбца m — количество поставщиков n — количество потребителей Xi,j — перевозка между поставщиком Aiи потребителем Bj.Поставщик Потребитель Запасы груза
B1
B2
B3
B4
B5
A1
14
8
17
5
3 370
A2
21
10
7
11
6 450
A3
3
5
8
4
9 480 Потребность 300 280 330 290 100
Транспортная задача имеет закрытыйтип, так как суммарный запас груза равен суммарным потребностям. Находимопорный план по правилу северо-западного угла: Введем некоторые обозначения: Ai* — излишек нераспределенного груза от поставщика Ai Bj* — недостача в поставке груза потребителю Bj
Помещаем в клетку (1,1) меньшее изчисел A1*=370 и B1*=300 Так какспрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем врасчет не принимается Помещаем в клетку (1,2) меньшее из чисел A1*=70и B2*=280 Так как запасы поставщика A1исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку(2,2) меньшее из чисел A2*=450 и B2*=210Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшемв расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A2*=240и B3*=330 Так как запасы поставщика A2исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку(3,3) меньшее из чисел A3*=480 и B3*=90Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшемв расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A3*=390и B4*=290 Так как спрос потребителя B4удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем вклетку (3,5) меньшее из чисел A3*=100 и B5*=100Поставщик Потребитель Запасы груза
B1
B2
B3
B4
B5
A1
14
300
8
70
17
5
3
370
A2
21
10
210
7
240
11
6
450
A3
3
5
8
90
4
290
9
100 480 Потребность 300 280 330 290 100
Целевая функция F=11320
Решаем задачу распределительнымметодом:
Этап 1
Определим значения оценок Si,jдля всех свободных клеток (неоптимальные выделены красным цветом). Дляэтого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла,складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком«плюс», в четных — со знаком «минус». S1,3 = c1,3-c1,2+c2,2-c2,3= 12 S1,4 = c1,4-c1,2+c2,2-c2,3+c3,3-c3,4= 4 S1,5 = c1,5-c1,2+c2,2-c2,3+c3,3-c3,5= -3 S2,1 = c2,1-c2,2+c1,2-c1,1= 5 S2,4 = c2,4-c2,3+c3,3-c3,4= 8 S2,5 = c2,5-c2,3+c3,3-c3,5= -2 S3,1 = c3,1-c3,3+c2,3-c2,2+c1,2-c1,1= -14 S3,2 = c3,2-c3,3+c2,3-c2,2= -6