Методы оптимальных решений (стр. 6 )

D = 3a + 2b + 5c → max

Кроме того, необходимо выполнение ограничений на ресурсы. Первый тип стали расходуется по 1 кг на деталь A, значит общие затраты на все детали а будут 1*a, на деталь B тратиться 2*b, и на деталь c тратится 1*с. Общие затраты стали первого типа не должны превышать 430 кг. Запишем ограничение:

a + 2b + c ≤ 430

Аналогично сформируются ограничения и по двум другим типам стали:

3a + 2c ≤ 460

a + 4b ≤ 420

Окончательно математическая модель задачи примет вид

D = 3a + 2b + 5c → max

a + 2b + c ≤ 430

3a + 2c ≤ 460

a + 4b ≤ 420

Будем решать ее симплекс-методом. Для этого необходимо преобразовать неравенства в равенства. Добавим в решение три мнимых переменных x, y и z из условия, что их добавление превращает неравенства в равенства. Получим:

a + 2b + c + х =

3a + 2c + y =

a + 4b + z =

В оптимизируемой функции D выбираем максимальный коэффициент. В нашем случае это 5 при переменной с. Смотрим отношения свободных членов уравнений из системы ограничений к коэффициенту при переменной с. В первом отношение 430/1 = 430, во втором 460/2 = 230, в третьем переменной с нет. Из этих отношений выбираем минимальное, это 230. Значит уравнение (2) оставим без изменения и из него выражаем переменную с и подставляем в (1) и (3).

3a + 2c + y = 460 (2*)

с = 230 – 3/2 a – 1/2 y

Подставляем в (1): a + 2b + 230 – 3/2 a – 1/2 y + x = 430

-1/2a + 2b – 1/2 y + x = 200 (1*)

В (3) нет переменной с, оно останется без изменений: a + 4b + z = 420 (3*)

Подставляем в функцию D: D* = 3a + 2b + 5c = 3a + 2b + 5 (230 – 3/2 a – 1/2 y) = -9/2a + 2b -5/2y + 1150

Функция D после преобразования имеет положительные коэффициенты (если все отрицательные – решение окончено). При переменной b максимальный положительный коэффициент. Записываем новую задачу.

D* = -9/2a + 2b - 5/2y + 1150 → max

-1/2a + 2b – 1/2 y + x = 200 (1*)

3a + 2c + y = 460 (2*)

a + 4b + z = 420 (3*)

Смотрим отношения свободных членов к коэффициентам при переменной b. В (1*) 200/2 = 100, в (2*) нет b, в (3*) 420/4 = 105. В уравнении (1*) минимальное отношение. Оставляем его без изменений и выражаем из него переменную b.

-1/2a + 2b – 1/2 y + x = 200 (1**)

b = 100 + 1/4a + 1/4 y – 1/2x

Подставляем в (3*): a + 4 (100 + ¼ a +1/4 y-1/2х) + z = 420

2a – 2x + y + z = 20 (3**)

В (2*) нет переменной b, оно без изменений:

3a + 2c + y = 460 (2**)

Подставляем в D** = -9/2a + 2 (100 + 1/4 a+1/4y-1/2x) - 5/2y + 1150 = -7/2a – 2y -1/4 x + 1350

В функции нет положительных переменных. Значит решение окончено.

Приравниваем к нулю все неизвестные в D**, т. е. a=y=x=0. Подставляем в уравнения (1**) – (2**)

Из (1**): 2b = 200, значит b=100.

Из (2**): 2с = 460, значит с=230.

Из (3*): z=20.

D** = 1350

Таким образом, производство товара A нерентабельно, a=0. Товара b необходимо производить в количестве 100 штук и товара C в количестве 230. Доход от продажи составит тогда 1350 у. е.

Значение мнимой переменной z=20 говорит о том, что будут остатки материалов.

Подробное решение транспортной задачи методом минимального элемента

На рынке работают 4 поставщика муки А1, А2, А3, А4. Их запасы 120, 80, 200 и 150 килограмм соответственно. Необходимо обеспечить 4 магазина М1, М2, М3, М4, которым требуется 100, 50, 230, 170 килограмм соответственно. Тариф на перевозку одного килограмма муки от поставщика А1 к магазину М1 равен 2 руб., к М2 4 руб., к М3 3 руб., к М4 5 руб. От поставщика А2: 1 руб., 3 руб., 4 руб., 7 руб. соответственно. От поставщика А3: 6 руб., 7 руб., 5 руб., 8 руб. соответственно. От поставщика А4: 3 руб., 1.5 руб., 4 руб., 3 руб. Найти оптимальное решение доставки продукции от поставщиков в магазины, минимизируя стоимость доставки.

Решение.

1.  Проверить сумму запасов поставщиков и потребностей магазинов:

Поставщики: 120 + 80 + 200 + 150 = 550

Магазины: 150 + 50 + 230 + 170 = 550

Должно выполняться равенство. Если нет, то вводят мнимого поставщика или магазин, на котором будут в последствии копиться остатки. Мы такой случай для простоты не рассматриваем, но он легко сводится к аналогичной задаче.

2.  Составляем таблицу.

Тарифы в ячейках

Магазин Поставщик	М1	М2	М3	М4	Запасы
А1	2	4	3	5	120
А2	1	3	4	7	80
А3	6	7	5	8	200
А4	3	1.5	4	3	150
Потребности	100	50	230	170

3.  Находим среди тарифов на перевозку минимальный. Это маршрут от А2 к М1 за 1 руб. Выделяем этот элемент подчеркиванием А2М1. У поставщика А2 всего 80 кг. М1 нужно 100. Значит по этому маршруту поедет 80 кг.

	М1	М2	М3	М4	Запасы
А1	2	4	3	5	120
А2	1 80	3	4	7	80
А3	6	7	5	8	200
А4	3	1,5	4	3	150
Надо	100 20	50	230	170

4.  Первый маршрут определили: А2 к М1 80 кг х 1 руб. = 80 руб. – цена маршрута. Отмечаем в этой ячейке сколько кг отправили. У поставщика А2 больше нет муки, значит из дальнейших расчетов мы его исключаем. Вычеркиваем (выделено серым) всю строку А2. Магазину М1 осталось докупить 20кг. Зачеркиваем 100, пишем 20.

5.  Из незачеркнутых (светлых) элементов снова выбираем самый маленький, т. е. самую низкую стоимость перевозки. Это маршрут А4 к М2. Выделяем его. Магазину М2 надо 50 кг. У поставщика есть 150. Значит по маршруту отправим 50 кг. Пишем в соответствующей клетке.

	М1	М2	М3	М4	Запасы
А1	2	4	3	5	120
А2	1 80	3	4	7	80
А3	6	7	5	8	200
А4	3	1.5 50	4	3	150 100
Надо	100 20	50	230	170

6.  Второй маршрут определили: А4 к М2 50 кг х 1.5 руб. = 75 руб. Магазину М2 больше муки не надо, значит его столбик вычеркиваем из рассмотрения. У поставщика А4 еще осталось 100 кг. Пишем это в его запасах.

7.  Из незачеркнутых (светлых) элементов снова выбираем минимальный. Это 2 руб. по маршруту от А1 к М1. Магазину М1 осталось докупить 20 кг, у поставщика А1 есть 120 кг, значит по маршруту поедет 20 кг.

	М1	М2	М3	М4	Запасы
А1	220	4	3	5	120 100
А2	1 80	3	4	7	80
А3	6	7	5	8	200
А4	3	1.550	4	3	150 100
Надо	100 20	50	230	170

8.  Третий маршрут определили: А1 к М1 20 кг Х 2 руб. = 40 руб. Магазину М1 больше муки не надо, значит вычеркиваем столбик из рассмотрения. У поставщика А1 еще осталось 100 кг. Пишем в его запасах.