Целочисленное программирование. Метод Гомори

Если на все или некоторые переменные Целочисленное программирование. Метод Гомори - student2.ru наложено условие дискретности, например целочисленности ( Целочисленное программирование. Метод Гомори - student2.ru ), то такие задачи рассматриваются в разделе математического программирования, называемого дискретным, в частности целочисленным,программированием.

Задача целочисленного линейного программирования записывается следующим образом:

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

Метод решения поставленной задачи, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности.

Если оптимальный план целочисленный, то он и будет решением всей задачи.

Если условие целочисленности не выполняется, то на основании последней симплекс-таблицы для базисной переменной, имеющей наибольшую дробную часть, строится дополнительное ограничение в следующем виде:

Целочисленное программирование. Метод Гомори - student2.ru ,

где {aij}, {bi} – дробные части чисел aij и bi.

Среди нецелых свободных членов выбирают тот, который имеет наибольшую дробную часть. Дополнительное ограничение преобразовывают в уравнение, вычитая из его левой части целую неотрицательную переменную, которую затем добавляют к последней симплексной таблице. Полученную расширенную задачу решают симплекс-методом, и находят новый план. Если он не является целочисленным, то по последней симплексной таблице составляют новое дополнительное ограничение, и решение повторяется. Если задача разрешима в целых числах, то оптимальный целочисленный план найден.

Задача не имеет целочисленного решения, если для дробного bi все aij в этой строке целые.

Замечание. Дробной частью числа {a}называют разность между этим числом и его целой частью, т. е. наибольшим целым, не превосходящим а:

Целочисленное программирование. Метод Гомори - student2.ru ,

где Целочисленное программирование. Метод Гомори - student2.ru –целая часть числа.

Например,

Целочисленное программирование. Метод Гомори - student2.ru ;

Целочисленное программирование. Метод Гомори - student2.ru ;

Целочисленное программирование. Метод Гомори - student2.ru .

Пример 9. Решить задачу

Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

Решение

Решая задачу симплекс-методом, получим оптимальный план Целочисленное программирование. Метод Гомори - student2.ru , в котором х1 и х2 – дробные (табл. 17).

Таблица 17

БП сБ А0 –1 –3
x1 x2 x3 x4 x5 x6
x3 –3
x2 –1 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
х1 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

Составим дополнительное ограничение для базисной переменной Целочисленное программирование. Метод Гомори - student2.ru , имеющей наибольшую дробную часть:

Целочисленное программирование. Метод Гомори - student2.ru

Находим дробные части:

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

Тогда ограничение примет вид

Целочисленное программирование. Метод Гомори - student2.ru

Преобразуем это неравенство в уравнение

Целочисленное программирование. Метод Гомори - student2.ru

где x7 ³ 0 и целое.

Введем искусственную базисную переменную x8 ³ 0 и целую. получим

Целочисленное программирование. Метод Гомори - student2.ru

На основании табл. 17 составим табл. 18 расширенной задачи.

Таблица 18

БП сБ А0 –1 –3 М  
x1 x2 x3 x4 x5 x6 x7 x8  
х3 –3  
x2 –1 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru  
х1 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru  
x8 М Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru –1 Целочисленное программирование. Метод Гомори - student2.ru
Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru  
  Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru –М  
              Целочисленное программирование. Метод Гомори - student2.ru      

Решаем расширенную задачу симплекс-методом. План, записанный в табл. 18, не является оптимальным. Выберем разрешающий столбец: Целочисленное программирование. Метод Гомори - student2.ru (например, шестой). Найдем Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru , т. е. возьмем разрешающую, например, четвертую строку. Итак, разрешающим элементом является Целочисленное программирование. Метод Гомори - student2.ru . Выполнив симплексные преобразования, придем к табл. 19.

Таблица 19

БП сБ А0 –1 –3
x1 x2 x3 x4 x5 x6 x7
x3 –3
x2 –1 –1
x1 –1 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
x6 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
Целочисленное программирование. Метод Гомори - student2.ru –15 –6 Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

Полученный план (0; 3; 4; 0; 0; 1) является оптимальным и целочисленным, а fmin = –15.

Ответ: x1 = 0; x2 = 3; x3 = 4; fmin = – 15.

Вопросы для самоконтроля

1. Постановка задач целочисленного линейного программирования: общей задачи о расписании; задачи коммивояжера; задач о разбиении, покрытии и упаковке; задачи о размещении оборудования; задачи раскроя.

2. Общая идея метода Гомори.

3. Алгоритм метода Гомори.

4. Суть метода ветвей и границ.

6. Нелинейное программирование.
Метод множителей Лагранжа

Если в задаче математического программирования целевая функция и (или) хотя бы одна из функций системы ограничений нелинейны, то такой раздел называется нелинейным программированием.

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

Метод Лагранжа активно используется для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.

Рассмотрим классическую задачу оптимизации

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

Функции Целочисленное программирование. Метод Гомори - student2.ru и Целочисленное программирование. Метод Гомори - student2.ru непрерывны и имеют частные производные, по крайней мере, второго порядка.

В простейшем случае условным экстремумом функции f(x1; x2) называется максимум или минимум этой функции, достигнутый при условии, что x1 и x2 удовлетворяют дополнительному условию (уравнению связи) φ(x1; x2) = b.

Условный экстремум функции f(x1; x2) при наличии дополнительного ограничения φ(x1; x2) = b находят с помощью так называемой функции Лагранжа

L(x1; x2; λ) = f(x1; x2) + λ · (b – φ(x1; x2)),

где λ – неотрицательный постоянный множитель (множитель Лагранжа).

Необходимое условие экстремума сводится к существованию решения системы трех уравнений с тремя неизвестными x1, x2, λ:

Целочисленное программирование. Метод Гомори - student2.ru

В результате решения системы находятся все стационарные точки функции Лагранжа.

Достаточное условие экстремума сводится к изучению знака второго дифференциала Целочисленное программирование. Метод Гомори - student2.ru функции Лагранжа

Целочисленное программирование. Метод Гомори - student2.ru

Функция f(x1; x2) имеет в стационарной точке (x1; x2; l) условный максимум, если в ней d2L < 0, и условный минимум, если d2L > 0.

Аналогично находится условный экстремум функции трех и большего числа переменных. Заметим, что второй дифференциал d2L функции Лагранжа для трех переменных имеет вид

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

Можно указать следующий порядок решения классической задачи оптимизации методом множителей Лагранжа:

1. составить функцию Лагранжа

L(x1; …; xn; λ) = f(x1; …; xn) + λ · (b – φ(x1; …; xn)).

2. найти частные производные функции Лагранжа по всем переменным x1, …, xn,l и приравнять их к нулю. Тем самым будет получена система, состоящая из n + 1 уравнений. Решить полученную систему (если это окажется возможным) и найти таким образом все стационарные точки функции Лагранжа.

3. из стационарных точек функции L, взятых без координаты l, выбрать точки, в которых функция f имеет условные экстремумы при наличии ограничения j(x1; …; xn) = b. Этот выбор осуществляется, например, с применением достаточного условия.

Пример 10. Найти условный экстремум функции f = 6 – 4x1 – 3x2, если Целочисленное программирование. Метод Гомори - student2.ru

Решение

Задачу выполняем в следующем порядке:

1. Составляем функцию Лагранжа:

Целочисленное программирование. Метод Гомори - student2.ru

2. Необходимые условия дают систему уравнений

Целочисленное программирование. Метод Гомори - student2.ru

Решая эту систему уравнений, находим

Целочисленное программирование. Метод Гомори - student2.ru

Целочисленное программирование. Метод Гомори - student2.ru

3. Так как Целочисленное программирование. Метод Гомори - student2.ru то Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

Если Целочисленное программирование. Метод Гомори - student2.ru то d2L > 0. значит, в точке Целочисленное программирование. Метод Гомори - student2.ru функция f имеет условный минимум.

Если же Целочисленное программирование. Метод Гомори - student2.ru то d2L < 0. значит, в точке Целочисленное программирование. Метод Гомори - student2.ru функция f имеет условный максимум.

При этом fmax = 11, fmin = 1.

Ответ: Целочисленное программирование. Метод Гомори - student2.ru

Вопросы для самоконтроля

1. Общая постановка задачи нелинейного программирования.

2. Суть метода Лагранжа, применяемого для решения классической оптимизационной задачи.

3. Составление функции Лагранжа.

4. Необходимое условие экстремума.

5. Достаточное условие экстремума.

6. Порядок решения классической задачи оптимизации методом множителей Лагранжа.

7. Метод динамического программирования.
Задача выбора кратчайшего пути

Задачи, в которых процесс выработки решения имеет многошаговый характер, решаются методами динамического программирования. Одна из таких задач – задача выбора кратчайшего пути, которая находит широкое применение в различных сферах деятельности. По сути решения аналогичными являются задачи выбора оптимальных схем транспортных перевозок, радиорелейных и телевизионных сетей, мелиорационных и ирригационных систем и т. п.

Пример 11. На сети дорог (рис. 11) указаны расстояния (в километрах) между промежуточными пунктами сети.

Целочисленное программирование. Метод Гомори - student2.ru

Рис. 11

Найти самый короткий маршрут из пункта 1 в пункт 10, составить таблицу оптимальных маршрутов из всех остальных пунктов сети в пункт 10 и указать кратчайшее расстояние от каждого пункта до пункта 10.

Решение

задаче необходимо придать шаговый характер. Разобьем все пункты сети на группы (табл. 20).

Таблица 20

Группы
1-я 2-я 3-я 4-я 5-я
     
   

К первой группе отнесем пункт 1; ко второй – пункты, в которые можно попасть непосредственно из пункта 1 (таковыми будут пункты 2, 3, 4); к третьей группе отнесем пункты, в которые можно попасть непосредственно из любого пункта второй группы (пункты 5, 6, 7) и т. д. В результате движение из пункта 1 в пункт 10 распадается на этапы.

На первом этапе необходимо из пункта 1 попасть в какой-нибудь пункт второй группы, на втором этапе – из пункта второй группы в пункт третьей группы и т. д.

В связи с этим маршрут из пункта 1 в пункт 10 разобьется на шаги. В данном случае этот процесс будет состоять из четырех шагов.

Будем оптимизировать каждый шаг, начиная с последнего, четвертого, при этом условные оптимальные шаговые решения пометим на сети стрелкой, выходящей из соответствующего кружка, а условный оптимальный эффект (в нашем случае это расстояние, которое следует преодолеть от данного пункта до пункта 10, двигаясь по оптимальному маршруту) запишем в нижнем кружке (рис. 12).

Целочисленное программирование. Метод Гомори - student2.ru

Рис. 12

На четвертом шаге в пункт 10 можно попасть из пункта 8 или 9, причем только одним способом: из пункта 8 – дорогой 8–10, при этом придется преодолеть 3 км, из пункта 9 – дорогой 9–10, преодолев
6 км. Результатом оптимизации четвертого шага являются первые две стрелки (на ребрах (8; 10) и (9; 10) сети).

Переходим к оптимизации третьего шага. Для этого проанализируем все возможные варианты движения из пунктов 5, 6, 7. Для каждого пункта выбираем условное оптимальное решение (оптимальный маршрут в пункт 10) и вычисляем соответствующее минимальное расстояние. Из пункта 5 можно следовать либо через пункт 8, либо через пункт 9. В первом случае расстояние равно 5 + 3 = 8 км, во втором – 7 + 6 = 13 км. Значит, условный оптимальный маршрут из пункта 5 в пункт 10 проходит через пункт 8. На ребре (5; 8) ставим стрелку, а в кружке 5 записываем минимальное расстояние 8 = 5 + 3, ребро (5; 9) остается без стрелки. Аналогично для пункта 6 находим условно-оптимальный маршрут 6–8–10 с расстоянием до пункта 10 в 5 км, для пункта 7 – условно-оптимальный маршрут 7–9–10 с расстоянием в 10 км.

Далее оптимизируем путь для второго шага процесса. Здесь находим оптимальный маршрут в пункт 10 из каждого пункта второй группы (2, 3, 4).

Для каждого из этих пунктов надо проанализировать все возможные маршруты из него и найти сумму расстояний до ближайшего пункта третьей группы и условно-минимальное расстояние на оптимальном продолжении пути в пункт 10 от этого пункта, которое найдено в результате оптимизации третьего шага. Из всех возможных маршрутов выбираем тот, для которого эта сумма меньше (если суммы равны, выбираем любой маршрут). Для пункта 2 оптимальным будет маршрут протяженностью в 15 км, проходящий через пункт 7, поскольку по этому маршруту получаем минимальную из сумм (9 + 8) и (5 + 10); для пункта 3 – маршрут, проходящий через пункт 6 с расстоянием 4 + 5 = 9 км; для пункта 4 – маршрут через пункт 6 с расстоянием 1 + 5 = 6 км.

Оптимизируем первый шаг. Сравним три возможных маршрута: через пункты 2, 3, 4. Устанавливаем, что наикратчайшим будет маршрут, пролегающий через пункт 4, как маршрут, отвечающий минимальной из сумм (3 + 15), (8 + 9), (4 + 6), равной 10.

Этап условной оптимизации закончен, и остается проследить оптимальный маршрут. Движение из пункта 1 по сети в направлении стрелок позволяет сформировать следующий самый короткий маршрут: 1–4–6–8–10. Его протяженность составляет 10 км. На рисунке он выделен жирной линией.

Примененный для решения задачи метод динамического программирования дает возможность одновременно с оптимальным маршрутом из пункта 1 в пункт 10 найти всю систему оптимальных маршрутов относительно пункта 10 для данной сети дорог. Все эти маршруты приведены в табл. 21.

Таблица 21

Исходный пункт Оптимальный путь в пункт 10, проходящий через пункты Кратчайшее расстояние
7 и 9
6 и 8
6 и 8

Вопросы для самоконтроля

1. Примеры задач динамического программирования, их особенности и геометрическая интерпретация.

2. Многошаговые процессы в динамических задачах.

3. Принцип оптимальности и рекуррентные соотношения.

4. Задача выбора кратчайшего пути и алгоритм ее решения.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Задание 1.Решить графически и методом искусственного базиса задачи линейного программирования.

1.1. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 1.6. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
1.2. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 1.7. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
1.3. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 1.8. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
1.4. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 1.9. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
1.5. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 1.10. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru

Задание 2. Решить задачу симплексным методом. Построить двойственную задачу и записать ее решение.

2.1. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 2.6. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
2.2. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 2.7. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
2.3. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 2.8. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
2.4. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 2.9. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
2.5. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 2.10. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru

Задание 3.Найти решение транспортной задачи.

3.1. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru 3.6. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
3.2. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru 3.7. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
3.3. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru 3.8. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
3.4. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru 3.9. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru
3.5. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru 3.10. Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

Задание 4.Найти методом Гомори максимум или минимум целевой функции при заданной системе ограничений. Во всех задачах Целочисленное программирование. Метод Гомори - student2.ru и Целочисленное программирование. Метод Гомори - student2.ru – целые Целочисленное программирование. Метод Гомори - student2.ru .

4.1. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 4.6. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
4.2. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 4.7. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
4.3. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 4.8. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
4.4. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 4.9. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru
4.5. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru 4.10. Целочисленное программирование. Метод Гомори - student2.ru ; Целочисленное программирование. Метод Гомори - student2.ru

Задание 5.С помощью метода Лагранжа найти точки условных экстремумов данных функций.

5.1. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.2. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.3. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.4. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.5. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.6. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.7. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.8. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.9. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .
5.10. Целочисленное программирование. Метод Гомори - student2.ru при Целочисленное программирование. Метод Гомори - student2.ru .

Задание 6. На рисунке показана сеть дорог. в таблице приведены расстояния (в километрах) между промежуточными пунктами сети.

Исходя из данных рисунка и таблицы выполнить следующее:

· методом динамического программирования найти самый короткий маршрут из пункта 1 в пункт 10;

· составить таблицу оптимальных маршрутов из всех остальных пунктов сети в пункт 10 и указать кратчайшее расстояние от каждого пункта до пункта 10.

Целочисленное программирование. Метод Гомори - student2.ru Целочисленное программирование. Метод Гомори - student2.ru

  Номер задания
6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10
С12
С13
С14
С25
С27
С35
С36
С37
С45
С46
С47
С58
С59
С68
С69
С79
С8,10
С9,10

ТЕСТЫ ДЛЯ ПРОВЕРКИ УСВОЕНИЯ
ТЕМ ПРОГРАММЫ КУРСА

Задания тестов рекомендуется выполнять по порядку. Если какое-либо задание не удается решить сразу, то необходимо перейти к следующему, а затем вернуться к пропущенному. При выполнении заданий разрешено пользоваться микрокалькулятором.

Тест 1 предусматривает выбор ответов из предложенных (задания закрытого типа 1.1–1.25), тест 2 – написание кратких ответов (задания открытого типа 2.1–2.4).

К каждому заданию теста 1 даны 5 вариантов ответов, из которых только 1 верный. В бланке ответов с номерами заданий следует поставить “+” в клетке, номер которой соответствует номеру выбранного ответа. Затем необходимо решить задания теста 2, ответы записав на бланке рядом с номерами заданий. После этого рекомендуется сравнить полученные результаты с приведенными в данном издании ответами.

Тест 1

1.1.На каком из чертежей отмеченная полуплоскость является решением неравенства Целочисленное программирование. Метод Гомори - student2.ru ?

х1
х2
х1
х2
1)

Целочисленное программирование. Метод Гомори - student2.ru

2) Целочисленное программирование. Метод Гомори - student2.ru
3) Целочисленное программирование. Метод Гомори - student2.ru 5) Целочисленное программирование. Метод Гомори - student2.ru
   
4) Целочисленное программирование. Метод Гомори - student2.ru  

1.2. Чему равны координаты вектора Целочисленное программирование. Метод Гомори - student2.ru , если функция Целочисленное программирование. Метод Гомори - student2.ru ?

Варианты ответа:

1) Целочисленное программирование. Метод Гомори - student2.ru ; 4) Целочисленное программирование. Метод Гомори - student2.ru ; 2) Целочисленное программирование. Метод Гомори - student2.ru ; 5) Целочисленное программирование. Метод Гомори - student2.ru . 3) Целочисленное программирование. Метод Гомори - student2.ru ;

1.3. На каком из чертежей линия Целочисленное программирование. Метод Гомори - student2.ru соответствует целевой функции Целочисленное программирование. Метод Гомори - student2.ru ?

1) Целочисленное программирование. Метод Гомори - student2.ru 2) Целочисленное программирование. Метод Гомори - student2.ru
3) Целочисленное программирование. Метод Гомори - student2.ru 5) Целочисленное программирование. Метод Гомори - student2.ru
4) Целочисленное программирование. Метод Гомори - student2.ru  

1.4. В задаче линейного программирования

Целочисленное программирование. Метод Гомори - student2.ru ;

Целочисленное программирование. Метод Гомори - student2.ru

построены область допустимых решений, вектор Целочисленное программирование. Метод Гомори - student2.ru и прямая Целочисленное программирование. Метод Гомори - student2.ru , что отражено на рисунке.

Указать координаты точки, в которой функция Целочисленное программирование. Метод Гомори - student2.ru достигает наибольшего значения.

Варианты ответа:

1) Целочисленное программирование. Метод Гомори - student2.ru ; 2) Целочисленное программирование. Метод Гомори - student2.ru ; 3) Целочисленное программирование. Метод Гомори - student2.ru ; 4) Целочисленное программирование. Метод Гомори - student2.ru ; 5) Целочисленное программирование. Метод Гомори - student2.ru .

–2х1 + х2 = 2
х1 = 4
1 + 4х2 = 18
х1
Целочисленное программирование. Метод Гомори - student2.ru

1.5. В каком из вариантов задача линейного программирования не имеет минимума?

1) Целочисленное программирование. Метод Гомори - student2.ru 2) Целочисленное программирование. Метод Гомори - student2.ru
3) Целочисленное программирование. Метод Гомори - student2.ru 5) Целочисленное программирование. Метод Гомори - student2.ru
4) Целочисленное программирование. Метод Гомори - student2.ru  

1.6. Указать, какой начальный опорный план был получен при решении симплексным методом задачи линейного программирования

Целочисленное программирование. Метод Гомори - student2.ru ;

Целочисленное программирование. Метод Гомори - student2.ru

Варианты ответа:

1) Целочисленное программирование. Метод Гомори - student2.ru ; 2) Целочисленное программирование. Метод Гомори - student2.ru ; 3) Целочисленное программирование. Метод Гомори - student2.ru ;
4) Целочисленное программирование. Метод Гомори - student2.ru ; 5) Целочисленное программирование. Метод Гомори - student2.ru .  

1.7. Условия ЗЛП

Целочисленное программирование. Метод Гомори - student2.ru ;

Целочисленное программирование. Метод Гомори - student2.ru

занесли в следующую симплексную таблицу:

БП сБ А0 x1 x2 x3 x4 x5  
 
x3 (2) Целочисленное программирование. Метод Гомори - student2.ru
x4  
x5  
Целочисленное программирование. Метод Гомори - student2.ru –6 –3  
      Целочисленное программирование. Метод Гомори - student2.ru          

Чему равен найденный разрешающий элемент?

Варианты ответа:

1) 2; 2) 7; 3) 9; 4) 4; 5) 1.

1.8. Вычислить по правилу прямоугольника элемент, стоящий на месте цифры 9 следующей таблицы:

БП сБ А0 x1 x2 x3 x4 x5

Наши рекомендации