Постановка задачи и её математическая модель

Некоторый однородный продукт, сосредоточенный у Постановка задачи и её математическая модель - 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 -му потребителю, тогда условие задачи можно записать в виде табл. 7.1, которую также называют матрицей планирования.

Таблица 3.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 Постановка задачи и её математическая модель - 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 единиц груза, то стоимость этой перевозки составит Постановка задачи и её математическая модель - student2.ru . Стоимость всего плана выразится двойной суммой Постановка задачи и её математическая модель - student2.ru .

Систему ограничений получаем из следующих условий:

а) все грузы должны быть вывезены, т.е. Постановка задачи и её математическая модель - student2.ru (эти уравнения получаются из строк);

б) все потребности должны быть удовлетворены, т.е. Постановка задачи и её математическая модель - student2.ru .

Таким образом, математическая модель транспортной задачи (ТЗ) может быть записана следующим образом:

– найти минимум линейной функции

Постановка задачи и её математическая модель - student2.ru (3.1)

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

Постановка задачи и её математическая модель - student2.ru (3.2)

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

Постановка задачи и её математическая модель - student2.ru . (3.3)

Такая задача называется задачей с правильным балансом, а её модель – закрытой. Если же равенство (3.3) не выполняется, то задача называется задачей с неправильным балансом, а её модель – открытой.

Теорема 3.1. Для того чтобы транспортная задача ЛП имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей .

Доказательство теоремы опускается.

3.2. Особенности решения транспортных задач с неправильным балансом:

1. Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е.

Постановка задачи и её математическая модель - student2.ru ,

то необходимо ввести фиктивного (n + 1)-го потребителя с запросами

Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru , равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза Постановка задачи и её математическая модель - student2.ru .

2. Если суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е.

Постановка задачи и её математическая модель - student2.ru ,

то необходимо ввести фиктивного (m+1)-го поставщика с запасами Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru , равными разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза Постановка задачи и её математическая модель - student2.ru .

3. При составлении начального опорного решения в последнюю очередь следует распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствует наименьшая стоимость перевозок, равная нулю.

Построение первоначального опорного плана

Рассмотрим систему ограничений (3.2) транспортной задачи. Она содержит Постановка задачи и её математическая модель - student2.ru неизвестных и Постановка задачи и её математическая модель - student2.ru уравнений, связанных соотношением (3.2). Если сложить почленно отдельно уравнения подсистемы в (3.2), то в силу (3.3) получим два одинаковых уравнения, что говорит о линейной зависимости всей системы. Однако если отбросить любое из этих уравнений, то получившаяся система из Постановка задачи и её математическая модель - student2.ru уравнений будет линейно независимой. Следовательно, опорный план транспортной задачи содержит Постановка задачи и её математическая модель - student2.ru компонент перевозок. Если условия транспортной задачи и её опорный план записаны в виде таблицы (например, табл. 3.1), то клетки, в которых проставлены перевозки, называют занятыми, а остальные – незанятыми. Занятие клетки соответствует базисным переменным, и их количество также равно Постановка задачи и её математическая модель - student2.ru .

Однако опорный план должен удовлетворять ещё и условию ацикличности. Для того, чтобы пояснить это понятие, рассмотрим вначале следующее определение:

Определение. Циклом называется набор клеток таблицы транспортной задачи Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru ,…, Постановка задачи и её математическая модель - student2.ru , в которой две и только две соседние клетки содержатся в одной строке или столбце, причём последняя находится в том же столбце, что и первая.

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

Метод северо-западного угла. Для наглядности рассмотрим данный метод на примере. Пусть условия транспортной задачи заданы табл. 3.2.

Таблица 3.2

Поставщики Потребители Запасы
Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru
Постановка задачи и её математическая модель - student2.ru          
         
Постановка задачи и её математическая модель - student2.ru          
         
Постановка задачи и её математическая модель - student2.ru          
         
Постановка задачи и её математическая модель - student2.ru          
         
Запросы

Заметим, что модель задачи является закрытой. Не учитывая стоимость перевозок, заполняем клетки, начиная с Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru таким образом, чтобы запросы всех потребителей удовлетворялись, а запасы всех поставщиков были бы вывезены. Итак, запас 1-го поставщика – 100 единиц товара, а запрос 1-го потребителя – 200. Поэтому в первую клетку 1-го столбца заносим Постановка задачи и её математическая модель - student2.ru , исключаем из рассмотрения первого поставщика ( его запасы вывезены) и переходим ко второму поставщику, у которого 250 единиц товара. Для того, чтобы удовлетворить первого потребителя, необходимо ещё 100 единиц. Поэтому в клетку Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru первого столбца заносим Постановка задачи и её математическая модель - student2.ru . Исключаем первого потребителя и переходим ко второму, запасы которого равны 200. У второго поставщика осталось 150 единиц товара, поэтому в клетку Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru заносим Постановка задачи и её математическая модель - student2.ru . Исключаем из рассмотрения второго поставщика и переходим к третьему. Этот процесс продолжается до тех пор, пока остаётся неисключённой в точности одна строка или один столбец. В результате получим табл. 3.3.

Таблица 3.3

Поставщики Потребители Запасы
Постановка задачи и её математическая модель - 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 из неисключённых клеток и т.д. При этом, если поставщик ещё не исключён, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь потом поставщик исключается из рассмотрения. Аналогично поступают и с потребителем.

Рассмотрим метод минимальной стоимости на примере табл. 3.2.

Наименьшую стоимость имеет клетка Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru . Запасы 1-го поставщика, как и запросы 4-го потребителя равны 100 единицам, поэтому заносим в эту клетку 100 и исключаем, например, 4-го потребителя. Затем переходим к следующей клетке, содержащей минимальную стоимость, например, к Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru . Запасы 2-го поставщика равны 200 единицам, а запросы 1-го потребителя – 250 единиц, поэтому в клетку заносим Постановка задачи и её математическая модель - student2.ru и исключаем 1-го потребителя. У 2-го поставщика остаётся ещё 50 единиц. Следующая клетка из неисключённых, соответствующая минимальной стоимости, находится на пересечении 3-й строки и 5-го столбца. Согласно тому же правилу, заносим в неё Постановка задачи и её математическая модель - student2.ru и исключаем 3-го поставщика и т.д. В результате получим табл. 3.4.

Таблица 3.4

Поставщики Потребители Запасы
Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru
Постановка задачи и её математическая модель - student2.ru          
     
Постановка задачи и её математическая модель - student2.ru          
     
Постановка задачи и её математическая модель - student2.ru          
       
Постановка задачи и её математическая модель - student2.ru          
   
Запросы

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

Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru .

Метод аппроксимации Фогеля. Данный метод из всех указанных позволяет построить решение, которое ближе к оптимальному. На каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди разностей выбирают максимальную. В строке (или столбце), которой данная максимальная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют количеством перевозимого груза на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце(строке).

Метод потенциалов

Из-за громоздкости симплексных таблиц, содержащих Постановка задачи и её математическая модель - student2.ru неизвестных, и большого объёма вычислительных работ для получения оптимального плана используются более простые методы. Самым распространённым является метод потенциалов.

Теорема 3.2. (признак оптимальности опорного решения). Если план опорный Постановка задачи и её математическая модель - student2.ru транспортной задачи является оптимальным, то ему соответствует совокупность Постановка задачи и её математическая модель - student2.ru чисел Постановка задачи и её математическая модель - student2.ru и Постановка задачи и её математическая модель - student2.ru чисел Постановка задачи и её математическая модель - student2.ru , удовлетворяющих условиям

Постановка задачи и её математическая модель - student2.ru (3.4)

для занятых клеток;

Постановка задачи и её математическая модель - student2.ru (3.5)

для свободных клеток.

Числа Постановка задачи и её математическая модель - student2.ru называются потенциалами поставщиков, а Постановка задачи и её математическая модель - student2.ru – потенциалами потребителей.

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

Рассмотрим алгоритм решения транспортных задач методом потенциалов:

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

2. Построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m + n – 1) и убедиться в линейной независимости векторов условий.

3. Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений

Постановка задачи и её математическая модель - student2.ru при xij > 0,

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

Постановка задачи и её математическая модель - student2.ru при xij > 0,

если известен потенциал vi , и

Постановка задачи и её математическая модель - student2.ru при xij > 0,

если известен потенциал uj.

4. Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам

Постановка задачи и её математическая модель - student2.ru

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

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

Постановка задачи и её математическая модель - student2.ru .

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «–», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину Постановка задачи и её математическая модель - student2.ru . Клетка со знаком «–», в которой достигается Постановка задачи и её математическая модель - student2.ru , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m + n – 1. Далее перейти к пункту 3 данного алгоритма.

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

Шаг 1. Составим систему соотношений: Постановка задачи и её математическая модель - student2.ru

соответствующих условиям (3.4). Система всегда содержит Постановка задачи и её математическая модель - student2.ru уравнений с Постановка задачи и её математическая модель - student2.ru неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределённой и одному неизвестному придают произвольное значение (обычно нулевое). После этого остальные потенциалы определяются однозначно. В нашем примере 4+5-1=8 уравнений с 9 неизвестными. Составленный нами первоначальный опорный план содержал нулевую переменную. В этом случае обычно определяют строку, содержащую наибольшее число занятых клеток. В нашем случае это Постановка задачи и её математическая модель - student2.ru . Положим Постановка задачи и её математическая модель - student2.ru . Из последних трёх соотношений системы определяем Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru и Постановка задачи и её математическая модель - student2.ru . Из остальных уравнений получаем Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru (табл. 3.5).

Таблица 3.5

Поставщики Потребители Запасы
Постановка задачи и её математическая модель - 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 Постановка задачи и её математическая модель - student2.ru          
       
Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru   Постановка задачи и её математическая модель - student2.ru Θ    
   
Запросы

Шаг 2. Проверим условие оптимальности для незанятых клеток. Если Постановка задачи и её математическая модель - student2.ru для всех таких клеток, то план является оптимальным, если же для некоторых Постановка задачи и её математическая модель - student2.ru , то план – неоптимальный. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину разности Постановка задачи и её математическая модель - student2.ru и записываем её значение в левый нижний угол этой клетки. Получилось 3 таких клетки: Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru .

Шаг 3.Теперь выбираем клетку, которую необходимо сделать базисной. Загрузке подлежит, в первую очередь, клетка, которой соответствует Постановка задачи и её математическая модель - student2.ru . В нашем случае это Постановка задачи и её математическая модель - student2.ru . Необходимо определить, сколько груза должно быть в неё распределено.

Шаг 4.Здесь необходимо выбрать клетку, которая выводится из базиса и определить величину перераспределения груза. Отмечаем знаком « + » незанятую клетку, которую надо загрузить. Вместе с ней в таблице стало Постановка задачи и её математическая модель - student2.ru занятых клеток, следовательно, появится цикл (причём единственный), все вершины которого, за исключением клетки, находятся в занятых клетках. Начинаем движение по этому циклу от клетки, отмеченной знаком , расставляя поочерёдно во всех вершинах, в которых он меняет направление, знаки « – » и « + ». Затем находим Постановка задачи и её математическая модель - student2.ru в клетках, отмеченных знаком «–». Эта величина определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение Постановка задачи и её математическая модель - student2.ru записываем в незанятую клетку, отмеченную знаком « + ». Двигаясь по циклу, вычитаем Постановка задачи и её математическая модель - student2.ru из объёмов перевозок в клетках, отмеченных знаком « – » и прибавляем к Постановка задачи и её математическая модель - student2.ru в клетках, отмеченных знаком « + ».

Итак, строим цикл, в клетку Постановка задачи и её математическая модель - student2.ru заносим 50единиц и перераспределяем груз (табл. 3.6). Исключаем из базисных переменных Постановка задачи и её математическая модель - student2.ru и вводим Постановка задачи и её математическая модель - student2.ru .

В результате перераспределения получили новый опорный невырожденный план, который снова подлежит проверке на оптимальность. Строим систему потенциалов:

Полагая Постановка задачи и её математическая модель - student2.ru , получим: Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru , Постановка задачи и её математическая модель - student2.ru .

Таблица 3.6

Поставщики Потребители Запасы
Постановка задачи и её математическая модель - 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 Постановка задачи и её математическая модель - student2.ru          
   
Запросы

Проверяя условие оптимальности, получаем, что оно выполняется во всех клетках. Следовательно, построенный план является оптимальным. Стоимость перевозки по нему Постановка задачи и её математическая модель - student2.ru Постановка задачи и её математическая модель - student2.ru .

Замечание. В настоящее время решение задач ЛП успешно реализуется на ПК в Excel, а именно, с помощью надстройки Excel − Поиск решения.

Контрольные вопросы и задания

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

2. Дайте определение задачи линейного программирования.

3. Сформулируйте математическую модель задачи использования ресурсов.

4. Используя графический метод решения задач линейного программирования определите максимальное или минимальное значения линейной целевой функции в области заданной неравенствами:

а) Постановка задачи и её математическая модель - student2.ru b) Постановка задачи и её математическая модель - student2.ru

5. Сформулируйте каноническую форму записи задачи линейного программирования.

6. Дайте определение многогранникав Постановка задачи и её математическая модель - student2.ru .

7. Какая точка множества называется угловой точкой?

8. Сформулируйте основную теорему ЛП.

9. Какое решение задачи ЛП называют опорным?. Укажите его связь с угловой точкой.

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

11. Решите задачу ЛП симплексным методом: Постановка задачи и её математическая модель - student2.ru .

12. Какими свойствами обладает двойственная задача ЛП?

13. Укажите правила составления двойственных задач.

14. Сформулируйте математическую модель транспортной задачи.

15. В чем заключается метод северо-западного угла построения первоначального опорного плана?

16. В чем заключается метод минимальной стоимости построения первоначального опорного плана?

17. В чем заключается метод аппроксимации Фогеляпостроения первоначального опорного плана?

18. Сформулируйте признак оптимальности опорного решениятранспортной задачи.

19. Построить первоначальный опорный план транспортной задачи методами: северо-западного угла, минимальной стоимости. В каждом случае вычислить общую стоимость перевозок грузов.

bj aj

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