транспортная задача. Решение Рассмотрим неравенство 1 системы ограничений. 3 x 1 2 x 2 6 Построим прямую 3 x 1 2 x 2 6
 Скачать 71.47 Kb.
|
|
Задача 1. Решить задачу линейного программирования графическим методом.   Решение: Рассмотрим неравенство 1 системы ограничений. 3 x1 + 2 x2 ≤ 6 Построим прямую: 3 x1+ 2 x2= 6 Пусть x1=0 => 2 x2= 6 => x2= 3 Пусть x2=0 => 3 x1= 6 => x1= 2 Найдены координаты двух точек (0, 3) и (2 ,0). Соединяем их и получаем необходимую прямую (1). Вернемся к исходному неравенству. 3 x1+ 2 x2≤ 6 Преобразуем неравенство, оставив в левой части только x2 2 x2≤ - 3 x1+ 6 x2≤ - 3/2 x1+ 3 Знак неравенства ≤. Следовательно, нас интересуют точки расположенные ниже построенной прямой (1). Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.  Рассмотрим неравенство 2 системы ограничений. x1- x2≥ 2 Построим прямую: x1- x2= 2 Пусть x1=0 => - x2= 2 => x2= -2 Пусть x2=0 => x1= 2 Найдены координаты двух точек (0, -2) и (2 ,0). Соединяем их и получаем необходимую прямую (2). Вернемся к исходному неравенству. x1- x2≥ 2 Преобразуем неравенство, оставив в левой части только x2 - x2≥ - x1+ 2 x2≤ x1- 2 Знак неравенства ≤. Следовательно, нас интересуют точки расположенные ниже построенной прямой (2). Объединим данное условие с предыдущим рисунком. Из рисунка видно, что область допустимых решений представляет собой одну точку A. Координаты точки A (2,0) известны.  Необходимо проверить, удовлетворяют ли координаты точки A (2,0) неравенству 3 системы ограничений? 0 * 2 + 1 * 0 ≥ 1 0 ≥ 1 не удовлетворяют. Ответ: Область допустимых решений - пустое множество. Задача 2. Решить транспортную задачу. С пяти сырьевых баз А1, …, А5 необходимо перевезти сырье на пять предприятий В1, …, В5. Известно количество сырья на каждой базе (аi) и потребность в сырье каждого предприятия (bj). Известны стоимости перевозок сырья с каждой базы на каждое предприятие (сij). Необходимо удовлетворить все потребности предприятий и определить оптимальный план перевозок, обеспечивающий минимальную стоимость плана перевозок. Начальный опорный план составлять методом минимальных тарифов, оптимизацию плана производить методом потенциалов. Номер варианта N задания соответствует порядковому номеру в журнале учета успеваемости. Для составления транспортной таблицы необходимо взять данные из всех столбцов таблицы со следующими номерами строк: N = N, N+1, N+2, N+3, N+4. Если (N + k) > 26, то номер строки равен (N + k) – 26, (k = 1, 2, 3, 4)
Решение:
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 23+41+28+37+41=170 ∑b = 30+45+32+34+29=170 Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей. Следовательно, модель исходной транспортной задачи является закрытой. Для решения задачи необходимо выполнение следующего условия: количество задействованных маршрутов = количество поставщиков + количество потребителей - 1. Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно. В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.
29 = min { 29, 41 }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||