Метод сравнения альтернатив для поиска первоначального решения транспортной задачи
Статья посвящена анализу и решению транспортной задачи линейного программирования. Цель работы - разработка и описание нового эффективного метода поиска первоначального распределения поставок, который в большинстве задач приводит к оптимальному решению.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 27.04.2021 |
| Размер файла | 30,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Метод сравнения альтернатив для поиска первоначального решения транспортной задачи
Т.Н. Зюзько
Государственный университет "Дубна", филиал "Протвино"
А.С. Курко
Московский технологический университет
Аннотация
Статья посвящена анализу и решению транспортной задачи линейного программирования. Целью работы является разработка и описание нового эффективного метода поиска первоначального распределения поставок, который в большинстве задач приводит к оптимальному решению.
Ключевые слова: логистика, транспортная задача, оптимизация перевозок, поиск первоначального решения, метод сравнения альтернатив.
Abstract
This article analyzes and solves linear programming formulation of transportation problem. The aim ofthis work is to create and describe new method ofchoosingfirst plan, which is directed to find effective solution of transportation problem, which is optimal in most of cases.
Key words: logistics, transportation problem, optimization of transportations, choosingfirst plan, method of comparing alternatives.
При автоматизации процессов предприятия и использовании линейного программирования для эффективного управления экономическими ресурсами, в особенности на крупных предприятиях, возникает необходимость в многократном периодическом решении транспортных задач. В связи с этим возникают затраты на обработку значительного количества информации, обоснованные большим количеством операций при определении наиболее оптимального распределения. Разработка эффективных алгоритмов решения транспортной задачи как ключевой задачи логистики позволяет увеличить эффективность управления производством, что отражается в экономии ресурсов при осуществлении перевозок.
Рассмотрим закрытую транспортную задачу. Как известно, поиск оптимального решения в данном типе начинается с выбора первоначального распределения поставок. На каждом следующем шаге решение оптимизируется [1; 2]. При случайном выборе первоначального решения процесс поиска оптимума может состоять из большого числа шагов. Для поиска первого опорного плана используются специальные методы. Такими методами являются метод северо-западного угла, правило минимального элемента, метод аппроксимации Фогеля, метод двойного предпочтения и другие [3]. Первоначальное решение, найденное по любому из перечисленных методов, может быть изначально оптимальным или далеким от оптимума в зависимости от условий задачи и специфики выбранного пути решения [4]. Опишем возможный вариант поиска первоначального распределения поставок. Назовем его методом сравнения альтернатив.
Для описания алгоритма поиска введем следующие определения. Назовем издержкой ячейки затраты на перевозку единицы груза от /-го поставщика к j-му потребителю. Альтернативная издержка для данной ячейки - коэффициент затрат для ячейки, находящейся в одной и той же строке или одном и том же столбце с рассматриваемой ячейкой. Минимальная альтернативная издержка по столбцу для данной ячейки - минимально возможный коэффициент затрат для ячейки, находящейся в одном и том же столбце с рассматриваемой ячейкой. Минимальная альтернативная издержка по строке для данной ячейки - минимально возможный коэффициент затрат для ячейки, находящейся в одной и той же строке относительно рассматриваемой ячейки. Если минимальные альтернативные издержки по строке и столбцу - одно и то же число, то минимальная альтернативная издержка равна этому числу. Если минимальные альтернативные издержки по строке и столбцу - разные числа, то минимальная альтернативная издержка для данной ячейки - наибольшее число из этих двух вариантов. Экономический смысл минимальной альтернативной издержки - количество условных единиц, которое необходимо потратить на поставку одной единицы товара в другую ячейку в случае отказа от поставки в рассматриваемую ячейку (от данного поставщика данному потребителю). Минимальная альтернативная сумма издержек для рассматриваемой ячейки - сумма минимальных альтернативных издержек по строке и столбцу для рассматриваемой ячейки. Полная альтернативная сумма для рассматриваемой ячейки - общие затраты на поставки необходимого по условиям количества товара (по соответствующей строке и столбцу) при условии, что в данную ячейку поставок не было. Минимальная полная альтернативная сумма для рассматриваемой ячейки - минимально возможные общие затраты на поставки необходимого по условиям количества товара (по соответствующей строке и столбцу) при условии, что в данную ячейку поставки не было. Полные затраты для ячейки - произведение цены поставки для данной ячейки и максимального количества товара, которое возможно поставить в эту ячейку по условиям.
Метод сравнения альтернатив состоит из трех этапов проверки, каждый из которых определяет, в какие ячейки возможно отправить максимальную поставку для получения оптимального или близкого к оптимальному первоначального решения. Чтобы определить, в какую ячейку нужно отправить поставку, нет необходимости проходить все три этапа. Часто происходит так, что ячейка для заполнения определяется на первом или втором этапах. Если же на первом этапе получено несколько возможных для поставки ячеек, то производится второй этап. Аналогично и для второго этапа. Опишем каждый этап.
Первый этап направлен на выбор среди ячеек с минимальным ценовым коэффициентом тех, минимальные альтернативные издержки которых максимальны. Этот признак означает, что при отказе от поставки в данные ячейки из-за необходимости выполнения ограничений поставка в другую ячейку будет иметь максимальную цену. Это значит, что расходы на заполнение другой ячейки при таком решении будут максимальны. Так как главная цель задачи - получение такого распределения, которое будет давать минимальные расходы, то эти ячейки наиболее целесообразно выбрать для поставки. транспортный линейный программирование
Если при реализации первого этапа получены несколько ячеек с одинаковыми минимальными альтернативными издержками, то производится второй этап. Он представляет собой выявление из полученных на первом этапе ячеек тех, минимальные альтернативные суммы которых максимальны. При отказе от поставки в данную ячейку, для того чтобы таблица была заполнена корректно и все ограничения были соблюдены, необходимо заполнить две или несколько ячеек. Отказ от поставки в ячейку обозначает, что соответствующий производитель не поставит, а потребитель не приобретет товар. Вследствие этого необходимо заполнить две или несколько других ячеек. Некоторые из них удовлетворят спрос данного потребителя, а остальные используют мощности данного поставщика. Единичная поставка в эти ячейки приведет к затратам, отражающимся в виде минимальной альтернативной суммы. Таким образом, осуществляется выбор тех ячеек, которые при отказе от заполнения приведут к максимальным расходам на единицу товара.
Пример 1 транспортной задачи
|
Спрос |
100 |
40 |
140 |
60 |
160 |
|
|
Предложение |
15 |
8 |
9 |
11 |
15 |
|
|
100 |
||||||
|
150 |
4 |
10 |
8 |
5 |
4 |
|
|
250 |
6 |
3 |
4 |
15 |
20 |
Если при прохождении второго этапа были получены несколько ячеек с одинаковыми альтернативными суммами, то реализуется третий этап. Он заключается в расчете и сравнении разностей минимальных полных альтернативных сумм и полных затрат для каждой из ячеек, найденных на предыдущем этапе. Минимальная полная альтернативная сумма в этом случае обозначает минимально возможные полные затраты на поставки в другие ячейки для удовлетворения спроса соответствующего данной ячейке потребителя и для использования мощностей соответствующего данной ячейке поставщика. Предполагая, что эта ячейка не будет заполнена, производятся последовательные поставки в другие ячейки, начиная с той, которая имеет минимальный коэффициент затрат, для удовлетворения ограничений. Другими словами, производится расчет того, сколько условных единиц всего необходимо минимально потратить с условием отказа от заполнения рассматриваемой ячейки. Разность между результатом этого расчета и полными затратами для данной ячейки представляет разницу между тем, сколько необходимо потратить всего условных единиц, если данную ячейку оставить пустой, и между тем, сколько необходимо всего потратить при заполнении этой ячейки. Данная разница представляет, насколько увеличатся общие расходы при отказе от заполнения указанной ячейки. Вот почему из всех сравниваемых ячеек выбираются те, для которых этот показатель максимален.
Приведем описание алгоритма поиска первоначального распределения поставок предложенным методом сравнения альтернатив.
Первый этап состоит в поиске ячейки для заполнения методом минимальных альтернативных затрат. Поиск ячеек для заполнения начинается с выбора тех ячеек, коэффициент затрат которых минимален. Если минимальной ценой поставки обладают несколько ячеек, то рассматриваем их, а если она одна, то рассмотрим эту ячейку и ячейку или ячейки со вторым минимумом. Для максимальной поставки выберем ту ячейку, минимальная альтернативная издержка которой максимальна. Если такая ячейка единственна, то поставка отправляется в нее и далее алгоритм повторяется заново с учетом ячеек с поставками, если таблица не заполнена. Если минимальные альтернативные издержки для нескольких ячеек одинаковы, производится переход на второй этап.
Второй этап - поиск ячейки для поставки методом минимальных альтернативных сумм издержек. Он применяется, когда на первом этапе были получены несколько ячеек, чьи минимальные альтернативные издержки одинаковы. Из них нужно выбрать те, у которых минимальная альтернативная сумма максимальна. В результате, если получена одна ячейка, то в нее отправляется максимальная поставка и алгоритм повторяется заново, если не достигнуто полное решение. Если получено несколько ячеек, проводится третий этап поиска.
Третий этап заключается в поиске ячейки для поставки методом разностей минимальных полных альтернативных сумм и полных затрат. Применяется в случае, когда в результате второго этапа были получены несколько ячеек, минимальные альтернативные суммы которых одинаковы. Для использования этого метода поясним, каким образом осуществляется поиск минимальных полных альтернативных сумм. Изначально выбирается ячейка из тех, которые были найдены на предыдущем этапе. Для нее производится расчет минимальной полной альтернативной суммы. Для этого по строке, где находится данная ячейка, выбирается ячейка, имеющая минимальный коэффициент затрат без учета данной ячейки, и для выбранной ячейки подсчитываются полные затраты. Если при такой поставке строка не закрыта, то выбирается следующая ячейка с минимальным коэффициентом затрат по строке, без учета рассматриваемой и уже заполненных на этом этапе ячеек. Так продолжается до тех пор, пока строка не закроется (ограничения не будут выполнены) или пока все ячейки, за исключением рассматриваемой, не будут содержать некоторую поставку. Аналогично производится расчет и по столбцу. После этого необходимо подсчитать сумму полных затрат для каждой ячейки, которые заполнялись на этом этапе (и по столбцу, и по строке). Данный показатель представляет собой минимальную полную альтернативную сумму. Далее производится подсчет полных затрат для данной ячейки. Разность между минимальной полной альтернативной суммой и полными затратами для данной ячейки есть коэффициент, по которому будет осуществлен выбор ячейки для заполнения. Для каждой ячейки, полученной на предыдущем этапе алгоритма, проводится расчет разности между минимальными полными альтернативными суммами и полными затратами. Для заполнения выбирается та ячейка, для которой этот коэффициент максимален.
Рассмотрим примеры решения задач данным методом
Пример 1 (табл. 1).
Т а б л и ц а 1 Матрица оценок свободных клеток для решения примера 2 методом аппроксимации Фогеля
|
0 |
3 |
1 |
0 |
|
|
-1 |
0 |
0 |
0 |
|
|
-1 |
0 |
1 |
0 |
1. Поиск первой ячейки.
1.1. Первый этап. Выбор ячеек (2,1), (2,5), (3,2), (3,3). Для них минимальные альтернативные издержки - 6, 15, 8, 8 соответственно, поэтому выбираем (2,5) для поставки (150 единиц товара). Закрывается вторая строка.
2. Поиск второй ячейки.
2.1. Первый этап. Выбор (3,2), (3,3). Для них минимальные альтернативные издержки - 8 и 9 соответственно. Выбор (3,3) для поставки (140 ед.). Закрывается третий столбец.
3. Поиск третьей ячейки.
3.1. Первый этап. Выбор (3,1) и (3,2). Для них минимальные альтернативные издержки - 15 и 8 соответственно, поэтому выбираем (3,1) для поставки (100 ед.). Закрывается первый столбец и третья строка.
4. Поиск четвертой ячейки.
4.1. Первый этап. Выбор (1,2) и (3,2). Для них минимальные альтернативные издержки - 11 и 15 соответственно, поэтому выбираем (3,2) для поставки (10 ед.).
Далее поставки однозначно определены условиями. Получим первоначальное решение (табл. 2), где в скобках указаны поставки.
При этом матрица оценок свободных клеток в результате будет следующей (табл. 3).
Это означает, что полученное решение является оптимальным распределением поставок. Решение данной задачи, найденное методами северо-западного угла, двойного предпочтения или минимального элемента будет неоптимальным. Заметим, что метод сравнения альтернатив не приводит к неоднозначности в отличие от метода минимального элемента, где возникает необходимость случайного выбора между ячейками с одинаковыми ценовыми коэффициентами (например, между (2,1), (2,5) и (3,3)).
Пример 2 (табл. 4).
Решим задачу методом аппроксимации Фогеля и рассмотрим полученное решение (табл. 5).
Т а б л и ц а 2 Первоначальное решение для примера 1
|
Спрос |
100 |
40 |
140 |
60 |
160 |
|
|
Предложе ние |
15 |
8 (30) |
9 |
11 (60) |
15 (10) |
|
|
100 |
||||||
|
150 |
4 |
10 |
8 |
5 |
4 (150) |
|
|
250 |
6 (100) |
3 (10) |
4 (140) |
15 |
20 |
Т а б л и ц а 3
Матрица оценок свободных клеток для примера 1
|
4 |
0 |
0 |
0 |
0 |
|
|
4 |
13 |
11 |
5 |
0 |
|
|
0 |
0 |
0 |
9 |
10 |
Т а б л и ц а 4 Пример 2 транспортной задачи
|
Спрос |
120 |
80 |
50 |
200 |
|
|
Предложение |
3 |
6 |
5 |
6 |
|
|
200 |
|||||
|
150 |
2 |
3 |
4 |
6 |
|
|
100 |
1 |
2 |
4 |
5 |
Т а б л и ц а 5 Первоначальное решение для примера 2, найденное методом аппроксимации Фогеля
|
Спрос |
120 |
80 |
50 |
200 |
|
|
Предложение |
3 (120) |
6 |
5 |
6 (80) |
|
|
200 |
|||||
|
150 |
2 |
3 |
4 (50) |
6 (100) |
|
|
100 |
1 |
2 (80) |
4 |
5 (20) |
Для проверки оптимальности была получена следующая матрица оценок свободных клеток (табл. 6).
Т а б л и ц а 6 Матрица оценок свободных клеток для примера с оптимальным решением
|
0 |
3 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
Полученное первоначальное решение является неоптимальным, причем общие расходы при таком распределении равны 1900.
Решим пример 2, используя метод сравнения альтернатив.
Т а б л и ц а 7
Первоначальное решение, найденное методом сравнения альтернатив для примера 2
|
Спрос |
120 |
80 |
50 |
200 |
|
|
Предложение |
3 |
6 |
5 (20) |
6 (180) |
|
|
200 |
|||||
|
150 |
2 (120) |
3 |
4 (30) |
6 |
|
|
100 |
1 |
2 (80) |
4 |
5 (20) |
1. Поиск первой ячейки.
1.1. Первый этап. Выбор ячеек (3,1), (2,1), (3,2). Для них минимальные альтернативные издержки - 2, 3, 3 соответственно, поэтому переходим ко второму этапу.
1.2. Второй этап. Выбор (2,1) и (3,2). Минимальные альтернативные суммы для (2,1) и (3,2) - 4 и 4. Переход к третьему этапу.
1.3. Третий этап. Выбор (2,1) и (3,2). Минимальные полные альтернативные суммы для (2,1) и (3,2) - 720 и 340 соответственно. Полные затраты для них - 240 и 160 соответственно. Разности между этими двумя показателями для (2,1) и (3,2) - 480 и 180 соответственно. Выбор (2,1) для поставки (120 ед.). Закрывается первый столбец.
2. Поиск второй ячейки.
2.1. Первый этап. Выбор (3,2) и (2,2). Для них минимальные альтернативные издержки - 4 и 4 соответственно. Переход ко второму этапу.
2.2. Второй этап. Выбор (3,2) и (2,2). Для них минимальные альтернативные суммы - 7 и 6 соответственно. Выбор (3,2) для поставки (80 ед.). Закрывается второй столбец.
3. Поиск третьей ячейки.
3.1. Первый этап. Выбор (3,3) и (2,3). Для них минимальные альтернативные издержки - 5 и 6 соответственно, поэтому выбираем (2,3) для поставки (30 ед.). Закрывается вторая строка.
4. Поиск четвертой ячейки.
4.1. Первый этап. Выбор (3,3), (1,3) и (3,4). Для них минимальные альтернативные издержки - 5, 6 и 6 соответственно, поэтому переходим ко второму этапу.
4.2. Второй этап. Выбор (1,3) и (3,4). Для них минимальные альтернативные суммы - 10 и 10. Переход к третьему этапу.
4.3. Третий этап. Выбор (1,3) и (3,4). Минимальные полные альтернативные суммы для (1,3) и (3,4) - 1280 и 1280. Полные затраты для них - 100 и 100. Разности между этими двумя показателями для (1,3) и (3,4) - 1180 и 1180. Выбор ячейки осуществляется случайно (в данном случае выбор не влияет на конечное решение). Выберем (1,3) для поставки (20 ед.).
Оставшиеся поставки однозначно определены условиями. Получим первоначальное решение (табл. 7).
Для проверки оптимальности была получена следующая матрица оценок свободных клеток (табл. 8).
Т а б л и ц а 8 Матрица оценок свободных клеток для решения примера 2 методом сравнения альтернатив
|
0 |
3 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
|
|
-1 |
0 |
0 |
0 |
Данное первоначальное решение не является оптимальным, общие затраты равны 1800. Однако оно ближе к оптимуму, чем решение, полученное методом аппроксимации Фогеля.
Особенностью этого примера является то, что большое количество ячеек имеет одинаковые коэффициенты затрат. Это создает большое количество неопределенностей, что сильно усложняет нахождение лучшего первоначального варианта распределения поставок при решении любым методом [5, 6].
Оценим эффективность предложенного метода. Подробное описание алгоритма решения предыдущего примера позволяет провести приближенную вероятностную оценку того, в скольких случаях используемый метод приведет к оптимальному решению. Допустим, что мы рассматриваем группу задач, спрос и предложение которых совпадают с примером 2, а коэффициенты затрат варьируются. Согласно матрице оценок свободных клеток, любое изменение коэффициентов затрат в ячейках может влиять на оптимальность решения. Оптимальному решению соответствует определенная матрица оценок свободных клеток (табл. 9).
Т а б л и ц а 8 Пример задачи, решение которой оптимально
|
Спрос |
120 |
80 |
50 |
200 |
|
|
Предложение |
|||||
|
200 |
3 |
6 |
5 |
6 |
|
|
150 |
2 |
3 |
4 |
6 |
|
|
100 |
2 |
2 |
4 |
5 |
Первоначальное решение этой задачи рассматриваемым методом не изменится в сравнении с примером 2, однако оно будет изначально оптимальным. Рассмотрим группу задач, решение которых данным методом состоит из базисных ячеек: (2,1), (3,2), (2,3), (1,3), (3,4) и (1,4) (в связи с неоднозначностей задачи существуют разные наборы базисных ячеек). Оно будет оптимальным, если матрица оценок свободных клеток будет состоять только из неотрицательных значений. При этом метод должен приводить к такому же набору базисных ячеек, так как другой набор обозначает другое решение. Коэффициенты затрат базисных ячеек остаются неизменными. Коэффициенты затрат свободных ячеек могут быть изменены при условии, что решение остается оптимальным. Таким образом, можно выявить совокупность задач, которые имеют оптимальные решения, получаемые данным методом. Количество таких задач будет использовано при вероятностной оценке эффективности. Проведем такой анализ.
Ячейка (1,1) может иметь коэффициент затрат больший или равный 3. Данная ячейка исключается из заполняемых на третьем этапе поиска первой ячейки для заполнения (пункт 1.3 решения примера 2). Такие варианты не приведут к отрицательным значениям в матрице оценок свободных клеток. Ячейка (3,1) также исключается при закрытии первого столбца. Она может содержать коэффициент затрат больший или равный 2, так как иные значения повлияют на решение (пункт 1.1 решения примера 2). Ячейка (1,2) исключается при закрытии второго столбца. Она может содержать издержку большую или равную 4, так как при значении 3 или меньше данная ячейка будет рассматриваться при выборе ячеек для заполнения на первом этапе поиска второй ячейки, что может изменить решение (пункт 2.1 в решении примера 2). Ячейка (2,2) может содержать издержку, равную только 3, так как это значение влияет на решение (это значение является минимальной альтернативной издержкой для ячеек (3,2), (2,1) в пункте 1.1 решения примера 2). Аналогично (3,3) может содержать только издержку, которая равна 4 (минимальная альтернативная издержка для (3,2) в пункте 2.1 решения примера 2). Ячейка (2,4) исключается при закрытии второй строки. Она может содержать издержку большую или равную 6, так как иные значения изменят решение (пункт 3.1 решения примера 2). Общее количество вариантов условий задач, при которых решение оптимально, можно определить произведением вариантов значений коэффициентов затрат для каждой ячейки. Пусть существует некое значение х, определяющее максимально возможный коэффициент затрат в каждой ячейке. Такое ограничение позволяет рассматривать конечную группу условий задач, приводящих к оптимальному решению при изменении каждого из коэффициентов. При этом количество этих условий определено числами (х-3), (х-2), (х-4), (х-6) (относительно каждой ячейки, коэффициент которой может быть изменен). Обозначим М произведение этих чисел. Оно представляет собой все возможные варианты задач с оптимальными решениями, получаемыми методом сравнения альтернатив. При этом общее количество рассматриваемых вариантов условий задач состоит из количества задач с оптимальным решением и количества условий, решение для которых может быть неоптимальным. Для оценки количества вариантов с возможным неоптимальным решением рассмотрим матрицу оценок свободных клеток. Любые изменения коэффициентов свободных клеток, обращающие значения в этой матрице в отрицательные или нулевые, определяют варианты условий, которые приведут или могут привести к неоптимальному решению. При таких условиях ячейка (1,1) может содержать значения от 0 до 2. Ячейка (1,2) - от 0 до 3. Ячейка (2,2) - от 0 до 2 и от 4 до х. Ячейка (2,4) - от 0 до 5. Ячейка (3,1) - от 0 до 1. Ячейка (3,3) - от 0 до 3 и от 5 до х. Из этого
К = 3 х 4 х (х - 1) х 6 х 2 х (х - 1) =
= 144 х (х - 1) х (х - 1),
где К - число примеров с явным неоптимальным решением. В этом случае общее число условий N равно сумме количества условий с оптимальным решением и количества условий с явным неоптимальным решением, т. е.
N = М + К = (х - 3) х (х - 2) х (х - 4) х
х (х - 6) + 144 х (х - 1) х (х - 1).
Тогда отношение числа задач с оптимальным решением к общему выделенному числу задач:
М / N = (х - 3) х (х - 2) х (х - 4) х
х (х - 6) / ((х - 3) х (х - 2) х (х - 4) х
х (х - 6) + 144 х (х - 1) х (х - 1)).
Данное отношение представляет собой вероятность получения оптимального решения при использовании метода сравнения альтернатив. Для расчета значения этого показателя необходимо взять некоторое значение х, отражающее, какую максимальную издержку может содержать ячейка в рассматриваемом наборе транспортных задач. Пусть х = 20, тогда вероятность при рассматриваемых условиях будет примерно равна 0,57.
Таким образом, метод сравнения альтернатив имеет следующие преимущества.
1. Метод применим к любому типу транспортных задач.
2. Он разрешает неопределенности, возникающие при использовании других известных методов, таких как метод минимального элемента и метод двойного предпочтения.
3. Во многих случаях рассмотренный метод дает наиболее близкое к оптимальному первоначальное решение в сравнении с некоторыми другими методами.
4. В рамках рассмотренной группы задач сделан вывод, что метод в 57 % случаев приводит к оптимальному первоначальному решению.
Использование представленного метода позволяет сократить количество шагов при решении транспортных задач линейного программирования, свести затраты на преобразование и хранение связанной с действиями поиска опорного плана информации к минимуму и, при долгосрочном применении, уменьшить объем данных для будущего анализа принятых решений.
Литература
1. Исследование операций в экономике: учеб. пособие для вузов / Н.Ш. Кремер [и др.] ; под ред. Н.Ш. Кремера. - 3-е изд., перераб. и доп. - М. : Юрайт, 2013. - 438 с.
2. Юдин Д.Б. Задачи и методы линейного программирования. Задачи транспортного типа / Д.Б. Юдин, Е.Г. Гольштейн. - М. : Либроком, 2010. - 184 с.
3. Ашманов С.А. Линейное программирование / С.А. Ашманов. - М. : Книга по Требованию, 2012. - 304 с.
4. Вентцель Е.С. Исследование операций: задачи, принципы, методология: учебник для вузов / Е.С. Вентцель. - М. : Дрофа, 2004. - 208 с.
Размещено на Allbest.ru
...Подобные документы
Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи.
курсовая работа [713,3 K], добавлен 19.10.2012Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Составление программы для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей. Алгоритм метода потенциалов. Пример решения транспортной задачи методом наименьшей стоимости.
отчет по практике [991,3 K], добавлен 06.12.2013Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Описание математических методов решения задачи оптимизации. Рассмотрение использования линейного программирования для решения транспортной задачи. Применение симплекс-метода, разработка разработать компьютерной модели в Microsoft Office Excel 2010.
курсовая работа [1,5 M], добавлен 24.05.2015Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.
курсовая работа [514,8 K], добавлен 04.02.2011Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.
курсовая работа [2,5 M], добавлен 22.11.2012Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Создание компьютерных программ. Сравнение C# с другими языками программирования. Решение задач транспортной логистики. Теория графов и структуры данных. Алгоритмы поиска маршрутов в графе. Выбор среды разработки. Редактирование транспортной сети.
курсовая работа [56,3 K], добавлен 08.10.2015Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.
курсовая работа [1000,7 K], добавлен 23.06.2012
